Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs

DOI10.1007/s00493-010-2455-9zbMath1240.68113MaRDI QIDQ653831

Lisa Zhang, Kunal Talwar, Julia Chuzhoy, Sanjeev Khanna, Venkatesan Guruswami, Matthew T. Andrews

Publication date: 19 December 2011

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-010-2455-9

zbMATH Keywords

approximation algorithm; constraint satisfaction problem; routing; randomized rounding; random hypergraph; all-or-nothing flow problem; approximability ratio; congestion minimization problem; disjoint paths problem with congestion; multicommodity flow relaxation

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C38: Paths and cycles

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

05C40: Connectivity

05C21: Flows in graphs

Related Items

Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs, Inapproximability of $H$-Transversal/Packing, Comments on: ``Static and dynamic source locations in undirected networks, Multicommodity flow in trees: packing via covering and iterated relaxation, The all-or-nothing flow problem in directed graphs with symmetric demand pairs, New tools and connections for exponential-time approximation, Routing with congestion in acyclic digraphs, Routing in Undirected Graphs with Constant Congestion, Hardness of Routing for Minimizing Superlinear Polynomial Cost in Directed Graphs, Maximum Throughput Network Routing Subject to Fair Flow Allocation, New Hardness Results for Routing on Disjoint Paths

Cites Work

• Primal-dual approximation algorithms for integral flow and multicut in trees
• Edge-disjoint paths in planar graphs
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• The directed subgraph homeomorphism problem
• Approximations for the disjoint paths problem in high-diameter planar networks
• An overtraining-resistant stochastic modeling method for pattern recognition
• Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
• Logarithmic hardness of the directed congestion minimization problem
• Edge-disjoint paths in Planar graphs with constant congestion
• A PCP characterization of NP with optimal amortized query complexity
• Multicommodity demand flow in a tree and packing integer programs
• The all-or-nothing multicommodity flow problem
• Multicommodity flow, well-linked terminals, and routing problems
• Hardness of the undirected edge-disjoint paths problem
• Hardness of the undirected congestion minimization problem
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• A Parallel Repetition Theorem
• The Nonapproximability of Non-Boolean Predicates
• Simple analysis of graph tests for linearity and PCP
• Approximability of Packing Disjoint Cycles
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item