Consecutive block minimization is 1.5-approximable

DOI10.1016/J.IPL.2008.04.009zbMATH Open1191.68865OpenAlexW2080076073MaRDI QIDQ975428FDOQ975428

Salim Haddadi, Zoubir Layouni

Publication date: 9 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.04.009

zbMATH Keywords

approximation algorithmstraveling salesmanconsecutive block minimizationpolynomial-time transformation

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cites Work

• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Title not available (Why is that?)
• On the hardness of approximating minimization problems
• Consecutive retrieval property -- revisited
• PC trees and circular-ones arrangements.
• Title not available (Why is that?)
• A structure theorem for the consecutive 1's property
• On the consecutive ones property
• A note on the NP-hardness of the consecutive block minimization problem
• Polynomial Complete Consecutive Information Retrieval Problems
• A Compact Storage Scheme for the Solution of Symmetric Linear Simultaneous Equations

Cited In (7)

• Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings
• On computing optimal linear diagrams
• Heuristic methods to consecutive block minimization
• Iterated local search for consecutive block minimization
• Polynomial-time local-improvement algorithm for consecutive block minimization
• Benders decomposition for set covering problems. Almost satisfying the consecutive ones property
• Exponential neighborhood search for consecutive block minimization

This page was built for publication: Consecutive block minimization is 1.5-approximable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q975428)