Polynomial-time local-improvement algorithm for consecutive block minimization

DOI10.1016/J.IPL.2015.02.010MaRDI QIDQ2345864zbMATH OpenOpenAlexFDO

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

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

approximation algorithmscombinatorial problemsconsecutive block minimizationlocal-improvement

Mathematics Subject Classification ID

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

Recommendations

• Iterated local search for consecutive block minimization
• Consecutive block minimization is 1.5-approximable
• A note on the NP-hardness of the consecutive block minimization problem
• Heuristic methods to consecutive block minimization
• Exponential neighborhood search for consecutive block minimization
• Maximum block improvement and polynomial optimization
• scientific article; zbMATH DE number 3922369
• Local algorithms for block-tree problems of discrete programming

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 1187154 (Why is no real title available?)
• scientific article; zbMATH DE number 3481821 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Compact Storage Scheme for the Solution of Symmetric Linear Simultaneous Equations
• A Simple Test for the Consecutive Ones Property
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• A new characterization of matrices with the consecutive ones property
• A note on the NP-hardness of the consecutive block minimization problem
• A structure theorem for the consecutive 1's property
• Consecutive block minimization is 1.5-approximable
• File organization
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• On Physical Mapping and the consecutive ones property for sparse matrices
• Organization of clustered files for consecutive retrieval
• Polynomial Complete Consecutive Information Retrieval Problems
• Set covering with almost consecutive ones property
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(8)

• Methods of local search for a problem on the permutation of the columns of a binary matrix
• Heuristic methods to consecutive block minimization
• Iterated local search for consecutive block minimization
• Minimising the number of gap-zeros in binary matrices
• Biased random-key genetic algorithm for scheduling identical parallel machines with tooling constraints
• Exponential neighborhood search for consecutive block minimization
• Low order polynomial bounds on the expected performance of local improvement algorithms
• Biased random-key genetic algorithm for the job sequencing and tool switching problem with non-identical parallel machines

This page was built for publication: Polynomial-time local-improvement algorithm for consecutive block minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345864)