Consecutive block minimization is 1.5-approximable

DOI10.1016/J.IPL.2008.04.009MaRDI QIDQ975428zbMATH OpenOpenAlexFDO

Authors 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

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

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)