Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

DOI10.1016/S0022-0000(03)00066-7zbMath1114.68430OpenAlexW2034269606MaRDI QIDQ5917535

Rajmohan Rajaraman, Bruce Shepherd, Sanjeev Khanna, Mihalis Yannakakis, Venkatesan Guruswami

Publication date: 19 August 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(03)00066-7

zbMATH Keywords

pathsApproximation algorithmsHardness of approximationMulticommodity flowNetwork routingBounded length edge-disjoint pathsEdge-disjointUnsplittable flowVertex-disjoint paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items

On the Max-flow min-cut ratio for directed multicommodity flows ⋮ Minimum \(k\) arborescences with bandwidth constraints ⋮ Hardness and approximation results for packing Steiner trees ⋮ Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation ⋮ The maximum integer multiterminal flow problem in directed graphs ⋮ On the disjoint paths problem ⋮ Finding disjoint paths with related path costs ⋮ All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs ⋮ Finding \(K\) dissimilar paths: single-commodity and discretized flow formulations ⋮ Finding multiple induced disjoint paths in general graphs ⋮ Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs ⋮ Paths of bounded length and their cuts: parameterized complexity and algorithms ⋮ Tree metrics and edge-disjoint \(S\)-paths ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity ⋮ Approximability of Packing Disjoint Cycles ⋮ The maximum edge-disjoint paths problem in complete graphs ⋮ Finding edge-disjoint paths in networks: an ant colony optimization algorithm ⋮ The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs ⋮ Dynamic routing and wavelength assignment for multi-lightpath demands ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Approximability of packing disjoint cycles ⋮ Maximum bipartite flow in networks with adaptive channel width ⋮ Maximum edge-disjoint paths in planar graphs with congestion 2 ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ On the approximability of time disjoint walks ⋮ On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ Randomized Rounding in the Presence of a Cardinality Constraint ⋮ Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms ⋮ Flows with unit path capacities and related packing and covering problems ⋮ A logarithmic approximation for unsplittable flow on line graphs ⋮ Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems

Cites Work

• 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
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• On the single-source unsplittable flow problem
• The directed subgraph homeomorphism problem
• Approximations for the disjoint paths problem in high-diameter planar networks
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Approximating low-congestion routing and column-restricted packing problems
• On the complexity of vertex-disjoint length-restricted path problems
• On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints
• On the Complexity of Timetable and Multicommodity Flow Problems
• Probability Inequalities for Sums of Bounded Random Variables
• Multi-Commodity Network Flows
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations