Set covering with almost consecutive ones property

DOI10.1016/J.DISOPT.2004.07.002MaRDI QIDQ2386204zbMATH OpenOpenAlexFDO

Authors Nikolaus Ruf, Anita Schöbel

Publication date 22 August 2005

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2004.07.002

zbMATH Keywords

AlgorithmBranch and boundSet coveringConsecutive ones property

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Operations research and management science (90B99)

Recommendations

• Benders decomposition for set covering problems. Almost satisfying the consecutive ones property
• Red-blue covering problems and the consecutive ones property
• Algorithms – ESA 2004
• Minimum Membership Set Covering and the Consecutive Ones Property
• Station location -- complexity and approximation

Cites work

• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1175963 (Why is no real title available?)
• A Heuristic Method for the Set Covering Problem
• Algorithms for railway crew management
• Algorithms for the set covering problem
• On the consecutive ones property
• On the hardness of approximating minimization problems
• Optimal Capacity Scheduling—I
• Solving hard set covering problems
• THE CONTINUOUS STOP LOCATION PROBLEM IN PUBLIC TRANSPORTATION NETWORKS
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The weighted consecutive ones problem for a fixed number of rows or columns.

Cited in

(17)

• Finding efficient make-to-order production and batch delivery schedules
• A faster algorithm for finding minimum Tucker submatrices
• The bus rapid transit investment problem
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• Locating stops along bus or railway lines -- a bicriteria problem
• Red-blue covering problems and the consecutive ones property
• Minimising the number of gap-zeros in binary matrices
• A polynomial-time algorithm for finding a minimal conflicting set containing a given row
• Station location -- complexity and approximation
• Stop location design in public transportation networks: covering and accessibility objectives
• Minimum power partial multi-cover on a line
• THE CONTINUOUS STOP LOCATION PROBLEM IN PUBLIC TRANSPORTATION NETWORKS
• Minimum Membership Set Covering and the Consecutive Ones Property
• Polynomial-time local-improvement algorithm for consecutive block minimization
• Benders decomposition for set covering problems. Almost satisfying the consecutive ones property
• Algorithms – ESA 2004
• Pairs Covered by a Sequence of Sets

This page was built for publication: Set covering with almost consecutive ones property

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