Consecutive block minimization is 1.5-approximable

DOI10.1016/j.ipl.2008.04.009zbMath1191.68865OpenAlexW2080076073MaRDI QIDQ975428

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

traveling salesmanapproximation algorithmsconsecutive block minimizationpolynomial-time transformation

Mathematics Subject Classification ID

Approximation algorithms (68W25)

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