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 (7)

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

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