Multicommodity flow in trees: packing via covering and iterated relaxation
DOI10.1007/s00453-012-9701-zzbMath1360.90259OpenAlexW2164903952MaRDI QIDQ528864
Publication date: 17 May 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9701-z
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) 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) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Flows in graphs (05C21)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximability of sparse integer programs
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- Primal-dual approximation algorithms for integral flow and multicut in trees
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
- Global wire routing in two-dimensional arrays
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- A polynomial algorithm for b-matchings: An alternative approach
- ``Integer-making theorems
- Conversion of coloring algorithms into maximum weight independent set algorithms
- \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Complexity of approximating bounded variants of optimization problems
- Path problems in generalized stars, complete graphs, and brick wall graphs
- On the disjoint paths problem
- Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph
- Iterative Packing for Demand and Hypergraph Matching
- Approximating the smallest k -edge connected spanning subgraph by LP-rounding
- Throughput Maximization for Periodic Packet Routing on Trees and Grids
- k-Edge-Connectivity: Approximation and LP Relaxation
- Approximating minimum bounded degree spanning trees to within one of optimal
- On Column-Restricted and Priority Covering Integer Programs
- Survivable Network Design with Degree or Order Constraints
- Multicommodity demand flow in a tree and packing integer programs
- Additive Guarantees for Degree-Bounded Directed Network Design
- Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
- On the Complexity of Timetable and Multicommodity Flow Problems
- On the approximability of the maximum common subgraph problem
- The Demand-Matching Problem
- Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow
- A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
