Poly-logarithmic approximation for maximum node disjoint paths with constant congestion

Chandra Chekuri; Alina Ene

doi:10.1137/1.9781611973105.24

Poly-logarithmic approximation for maximum node disjoint paths with constant congestion

Chandra Chekuri, Alina Ene

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We consider the Maximum Node Disjoint Paths (MNDP) problem in undirected graphs. The input consists of an undirected graph G = (V, E) and a collection {(s₁,t₁),..., (s_k,t_k)} of k source-sink pairs. The goal is to select a maximum cardinality subset of pairs that can be routed/connected via node-disjoint paths. A relaxed version of MNDP allows up to c paths to use a node, where c is the congestion parameter. We give a polynomial time algorithm that routes Ω(OPT/poly log k) pairs with O(1) congestion, where OPT is the value of an optimum fractional solution to a natural multicommodity flow relaxation. Our result builds on the recent breakthrough of Chuzhoy [17] who gave the first polylogarithmic approximation with constant congestion for the Maximum Edge Disjoint Paths (MEDP) problem.

Original language	English (US)
Title of host publication	Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Publisher	Association for Computing Machinery
Pages	326-341
Number of pages	16
ISBN (Print)	9781611972511
DOIs	https://doi.org/10.1137/1.9781611973105.24
State	Published - 2013
Event	24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 - New Orleans, LA, United States Duration: Jan 6 2013 → Jan 8 2013

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other	24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Country/Territory	United States
City	New Orleans, LA
Period	1/6/13 → 1/8/13

ASJC Scopus subject areas

Software
General Mathematics

Online availability

10.1137/1.9781611973105.24

Library availability

Discover UIUC Full Text

Cite this

Chekuri, C., & Ene, A. (2013). Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 (pp. 326-341). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973105.24

Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. / Chekuri, Chandra; Ene, Alina.
Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. Association for Computing Machinery, 2013. p. 326-341 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chekuri, C & Ene, A 2013, Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 326-341, 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, LA, United States, 1/6/13. https://doi.org/10.1137/1.9781611973105.24

@inproceedings{cb324de57c564e5398bb91b469952513,

title = "Poly-logarithmic approximation for maximum node disjoint paths with constant congestion",

abstract = "We consider the Maximum Node Disjoint Paths (MNDP) problem in undirected graphs. The input consists of an undirected graph G = (V, E) and a collection {(s1,t1),..., (sk,tk)} of k source-sink pairs. The goal is to select a maximum cardinality subset of pairs that can be routed/connected via node-disjoint paths. A relaxed version of MNDP allows up to c paths to use a node, where c is the congestion parameter. We give a polynomial time algorithm that routes Ω(OPT/poly log k) pairs with O(1) congestion, where OPT is the value of an optimum fractional solution to a natural multicommodity flow relaxation. Our result builds on the recent breakthrough of Chuzhoy [17] who gave the first polylogarithmic approximation with constant congestion for the Maximum Edge Disjoint Paths (MEDP) problem.",

author = "Chandra Chekuri and Alina Ene",

year = "2013",

doi = "10.1137/1.9781611973105.24",

language = "English (US)",

isbn = "9781611972511",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "326--341",

booktitle = "Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013",

address = "United States",

note = "24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 ; Conference date: 06-01-2013 Through 08-01-2013",

}

TY - GEN

T1 - Poly-logarithmic approximation for maximum node disjoint paths with constant congestion

AU - Chekuri, Chandra

AU - Ene, Alina

PY - 2013

Y1 - 2013

N2 - We consider the Maximum Node Disjoint Paths (MNDP) problem in undirected graphs. The input consists of an undirected graph G = (V, E) and a collection {(s1,t1),..., (sk,tk)} of k source-sink pairs. The goal is to select a maximum cardinality subset of pairs that can be routed/connected via node-disjoint paths. A relaxed version of MNDP allows up to c paths to use a node, where c is the congestion parameter. We give a polynomial time algorithm that routes Ω(OPT/poly log k) pairs with O(1) congestion, where OPT is the value of an optimum fractional solution to a natural multicommodity flow relaxation. Our result builds on the recent breakthrough of Chuzhoy [17] who gave the first polylogarithmic approximation with constant congestion for the Maximum Edge Disjoint Paths (MEDP) problem.

AB - We consider the Maximum Node Disjoint Paths (MNDP) problem in undirected graphs. The input consists of an undirected graph G = (V, E) and a collection {(s1,t1),..., (sk,tk)} of k source-sink pairs. The goal is to select a maximum cardinality subset of pairs that can be routed/connected via node-disjoint paths. A relaxed version of MNDP allows up to c paths to use a node, where c is the congestion parameter. We give a polynomial time algorithm that routes Ω(OPT/poly log k) pairs with O(1) congestion, where OPT is the value of an optimum fractional solution to a natural multicommodity flow relaxation. Our result builds on the recent breakthrough of Chuzhoy [17] who gave the first polylogarithmic approximation with constant congestion for the Maximum Edge Disjoint Paths (MEDP) problem.

UR - http://www.scopus.com/inward/record.url?scp=84876018864&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84876018864&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973105.24

DO - 10.1137/1.9781611973105.24

M3 - Conference contribution

AN - SCOPUS:84876018864

SN - 9781611972511

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 326

EP - 341

BT - Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

PB - Association for Computing Machinery

T2 - 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

Y2 - 6 January 2013 through 8 January 2013

ER -

Poly-logarithmic approximation for maximum node disjoint paths with constant congestion

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this