New Hardness Results for Routing on Disjoint Paths
From MaRDI portal
Publication:3387753
DOI10.1137/17M1146580zbMath1497.68221arXiv1611.05429OpenAlexW3113475418MaRDI QIDQ3387753
Rachit Nimavat, David H. Kim, Julia Chuzhoy
Publication date: 13 January 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.05429
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Approximations for the disjoint paths problem in high-diameter planar networks
- Approximating disjoint-path problems using packing integer programs
- Graph minors. XIII: The disjoint paths problem
- Routing in Undirected Graphs with Constant Congestion
- Edge-disjoint paths in Planar graphs with constant congestion
- An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs
- Proof verification and the hardness of approximation problems
- A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
- Multicommodity flow, well-linked terminals, and routing problems
- Hardness of the undirected edge-disjoint paths problem
- Probabilistic checking of proofs
- On the Computational Complexity of Combinatorial Problems
- On the Complexity of Timetable and Multicommodity Flow Problems
- Almost polynomial hardness of node-disjoint paths in grids
- On Approximating Node-Disjoint Paths in Grids
- Improved approximation for node-disjoint paths in planar graphs
- Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
- Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion
- Edge Disjoint Paths in Moderately Connected Graphs
