Minimising the number of gap-zeros in binary matrices

DOI10.1016/J.EJOR.2013.01.028MaRDI QIDQ2355802zbMATHOpenAlexDBLPWikidataFDO

Authors Konstantin Chakhlevitch, C. A. Glass, N. V. Shakhlevich

Publication date 28 July 2015

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL http://eprints.whiterose.ac.uk/79240/1/ChakhlevitchGlassShakhlevich.pdf

zbMATH Keywords

heuristicscombinatorial optimisationschedulingconsecutive ones propertybinary matrices

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Boolean programming (90C09)

Recommendations

• Heuristic methods to consecutive block minimization
• Approximation of the Consecutive Ones Matrix Augmentation Problem
• Polynomial-time local-improvement algorithm for consecutive block minimization
• Iterated local search for consecutive block minimization
• Optimal patchings for consecutive ones matrices

Cites work

• scientific article; zbMATH DE number 1003281 (Why is no real title available?)
• scientific article; zbMATH DE number 5606342 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2003406 (Why is no real title available?)
• A Simple Test for the Consecutive Ones Property
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• A note on the consecutive ones submatrix problem.
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• Approximation of the Consecutive Ones Matrix Augmentation Problem
• Batch machine production with perishability time windows and limited batch size
• File organization
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• On Physical Mapping and the consecutive ones property for sparse matrices
• Physical mapping of chromosomes: A combinatorial problem in molecular biology
• 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
• The consecutive ones submatrix problem for sparse matrices
• The weighted consecutive ones problem for a fixed number of rows or columns.

Cited in

(5)

• scientific article; zbMATH DE number 4162290 (Why is no real title available?)
• Heuristic methods to consecutive block minimization
• Iterated local search for consecutive block minimization
• The maximum matrix contraction problem
• Eliminating switching components in binary matrices by 0-1 flips and column permutations

This page was built for publication: Minimising the number of gap-zeros in binary matrices

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