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

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

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

Publication date: 19 August 2004

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

zbMATH Keywords

paths; Approximation algorithms; Hardness of approximation; Multicommodity flow; Network routing; Bounded length edge-disjoint paths; Edge-disjoint; Unsplittable flow; Vertex-disjoint paths

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

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

68W25: Approximation algorithms

05C20: Directed graphs (digraphs), tournaments

Related Items

Approximability of Packing Disjoint Cycles, Approximability of packing disjoint cycles, Maximum bipartite flow in networks with adaptive channel width, On the Max-flow min-cut ratio for directed multicommodity flows, Finding disjoint paths with related path costs, Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity, The maximum edge-disjoint paths problem in complete graphs, Flows with unit path capacities and related packing and covering problems, Minimum \(k\) arborescences with bandwidth constraints, Hardness and approximation results for packing Steiner trees, Finding edge-disjoint paths in networks: an ant colony optimization algorithm, 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, Dynamic routing and wavelength assignment for multi-lightpath demands, Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms

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