A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

DOI10.1145/2893472MaRDI QIDQ3177821zbMATH OpenOpenAlexFDO

Authors Julia Chuzhoy, Shi Li

Publication date 2 August 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.1272

zbMATH Keywords

approximation algorithmsedge-disjoint pathsrouting problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Paths and cycles (05C38)

Abstract: In the Edge-Disjoint Paths with Congestion problem (EDPwC), we are given an undirected n-vertex graph G, a collection M={(s_1,t_1),...,(s_k,t_k)} of demand pairs and an integer c. The goal is to connect the maximum possible number of the demand pairs by paths, so that the maximum edge congestion - the number of paths sharing any edge - is bounded by c. When the maximum allowed congestion is c=1, this is the classical Edge-Disjoint Paths problem (EDP). The best current approximation algorithm for EDP achieves an $O(sqrtn)$-approximation, by rounding the standard multi-commodity flow relaxation of the problem. This matches the $Omega(sqrtn)$ lower bound on the integrality gap of this relaxation. We show an $O(polylogk)$-approximation algorithm for EDPwC with congestion c=2, by rounding the same multi-commodity flow relaxation. This gives the best possible congestion for a sub-polynomial approximation of EDPwC via this relaxation. Our results are also close to optimal in terms of the number of pairs routed, since EDPwC is known to be hard to approximate to within a factor of $ildeOmega((logn{)}^{1/(c+1)})$ for any constant congestion c. Prior to our work, the best approximation factor for EDPwC with congestion 2 was $ildeO(n^{3/7})$, and the best algorithm achieving a polylogarithmic approximation required congestion 14.

Recommendations

• An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion Two
• Breaking \(o(n^{1/2})\)-approximation algorithms for the edge-disjoint paths problem with congestion two
• Poly-logarithmic approximation for maximum node disjoint paths with constant congestion
• Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• A polylogarithmic approximation algorithm for 2-edge-connected dominating set
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths

Cited in

(23)

• Routing in undirected graphs with constant congestion
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
• Approximation algorithms for round-UFP and round-SAP
• Packing directed cycles quarter- and half-integrally
• Approximation algorithms and hardness of integral concurrent flow
• Edge-disjoint paths in planar graphs with constant congestion
• The fractional congestion bound for efficient edge disjoint routing
• Edge-disjoint paths in planar graphs with constant congestion
• Constant congestion routing of symmetric demands in planar directed graphs
• Planar Digraphs
• All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs
• Tight approximation and kernelization bounds for vertex-disjoint shortest paths
• Algorithmic properties of sparse digraphs
• Maximum edge-disjoint paths in k-sums of graphs
• Improved approximation for node-disjoint paths in grids with sources on the boundary
• Congestion minimization for multipath routing via multiroute flows
• On the \(k\) edge-disjoint 2-hop-constrained paths polytope
• scientific article; zbMATH DE number 7525509 (Why is no real title available?)
• Routing in undirected graphs with constant congestion
• Poly-logarithmic approximation for maximum node disjoint paths with constant congestion
• Almost polynomial hardness of node-disjoint paths in grids
• An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion Two
• New hardness results for routing on disjoint paths

This page was built for publication: A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177821)