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

DOI10.1007/s00493-010-2455-9zbMath1240.68113OpenAlexW2122997342MaRDI 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 algorithmconstraint satisfaction problemroutingrandomized roundingrandom hypergraphall-or-nothing flow problemapproximability ratiocongestion minimization problemdisjoint paths problem with congestionmulticommodity flow relaxation

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Connectivity (05C40) Flows in graphs (05C21)

Related Items (17)

Maximum Throughput Network Routing Subject to Fair Flow Allocation ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ Inapproximability of $H$-Transversal/Packing ⋮ The all-or-nothing flow problem in directed graphs with symmetric demand pairs ⋮ Approximating maximum integral multiflows on bounded genus graphs ⋮ Unnamed Item ⋮ Hardness of Routing for Minimizing Superlinear Polynomial Cost in Directed Graphs ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Unnamed Item ⋮ New tools and connections for exponential-time approximation ⋮ Routing with congestion in acyclic digraphs ⋮ Maximum edge-disjoint paths in planar graphs with congestion 2 ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ New Hardness Results for Routing on Disjoint Paths ⋮ Comments on: ``Static and dynamic source locations in undirected networks ⋮ Unnamed Item ⋮ Electrical flows over spanning trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs