Set covering with almost consecutive ones property

DOI10.1016/j.disopt.2004.07.002zbMath1087.90046OpenAlexW2158406182MaRDI QIDQ2386204

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)

Related Items (12)

Stop location design in public transportation networks: covering and accessibility objectives ⋮ Minimum power partial multi-cover on a line ⋮ A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row ⋮ Finding efficient make-to-order production and batch delivery schedules ⋮ Benders decomposition for set covering problems. Almost satisfying the consecutive ones property ⋮ A faster algorithm for finding minimum Tucker submatrices ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ THE CONTINUOUS STOP LOCATION PROBLEM IN PUBLIC TRANSPORTATION NETWORKS ⋮ Red-blue covering problems and the consecutive ones property ⋮ Polynomial-time local-improvement algorithm for consecutive block minimization ⋮ Minimising the number of gap-zeros in binary matrices ⋮ Locating stops along bus or railway lines -- a bicriteria problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the consecutive ones property
• Algorithms for railway crew management
• The weighted consecutive ones problem for a fixed number of rows or columns.
• Solving hard set covering problems
• THE CONTINUOUS STOP LOCATION PROBLEM IN PUBLIC TRANSPORTATION NETWORKS
• Optimal Capacity Scheduling—I
• On the hardness of approximating minimization problems
• A Heuristic Method for the Set Covering Problem
• Algorithms for the set covering problem

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