Consecutive block minimization is 1.5-approximable
From MaRDI portal
Publication:975428
DOI10.1016/j.ipl.2008.04.009zbMath1191.68865OpenAlexW2080076073MaRDI QIDQ975428
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
traveling salesmanapproximation algorithmsconsecutive block minimizationpolynomial-time transformation
Related Items
Heuristic methods to consecutive block minimization, Iterated local search for consecutive block minimization, Exponential neighborhood search for consecutive block minimization, On computing optimal linear diagrams, Benders decomposition for set covering problems. Almost satisfying the consecutive ones property, Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings, Polynomial-time local-improvement algorithm for consecutive block minimization
Cites Work
- Unnamed Item
- Unnamed Item
- Consecutive retrieval property -- revisited
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- On the consecutive ones property
- PC trees and circular-ones arrangements.
- A structure theorem for the consecutive 1's property
- Polynomial Complete Consecutive Information Retrieval Problems
- On the hardness of approximating minimization problems
- A note on the NP-hardness of the consecutive block minimization problem
- A Compact Storage Scheme for the Solution of Symmetric Linear Simultaneous Equations