Flows with Unit Path Capacities and Related Packing and Covering Problems

DOI10.1007/978-3-540-85097-7_17zbMath1168.90589OpenAlexW1877680583MaRDI QIDQ5505656

Martin Skutella, Maren Martens

Publication date: 27 January 2009

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://depositonce.tu-berlin.de/handle/11303/15639

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
• Maximal Flow Through a Network
• Handbook of Approximation Algorithms and Metaheuristics
• The Complexity of Enumeration and Reliability Problems
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Flows on few paths: Algorithms and lower bounds
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems