Polynomial-time local-improvement algorithm for consecutive block minimization

DOI10.1016/j.ipl.2015.02.010zbMath1328.68302OpenAlexW2068781124MaRDI QIDQ2345864

Salim Haddadi, F. Guessoum, S. Chenche, Meryem Cheraitia

Publication date: 21 May 2015

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

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

zbMATH Keywords

combinatorial problemsapproximation algorithmsconsecutive block minimizationlocal-improvement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items

Heuristic methods to consecutive block minimization, Iterated local search for consecutive block minimization, Biased random-key genetic algorithm for scheduling identical parallel machines with tooling constraints, Exponential neighborhood search for consecutive block minimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new characterization of matrices with the consecutive ones property
• Consecutive block minimization is 1.5-approximable
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Set covering with almost consecutive ones property
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• A structure theorem for the consecutive 1's property
• A Simple Test for the Consecutive Ones Property
• Organization of clustered files for consecutive retrieval
• Polynomial Complete Consecutive Information Retrieval Problems
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• A note on the NP-hardness of the consecutive block minimization problem
• A Compact Storage Scheme for the Solution of Symmetric Linear Simultaneous Equations
• File organization
• On Physical Mapping and the consecutive ones property for sparse matrices