Polynomial-time local-improvement algorithm for consecutive block minimization

DOI10.1016/J.IPL.2015.02.010zbMATH Open1328.68302OpenAlexW2068781124MaRDI QIDQ2345864FDOQ2345864

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

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

zbMATH Keywords

approximation algorithmscombinatorial problemsconsecutive block minimizationlocal-improvement

Mathematics Subject Classification ID

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

Cites Work

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

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)