A quasi-PTAS for unsplittable flow on line graphs

Nikhil Bansal; Amit Chakrabarti; Amir Epstein; Baruch Schieber

doi:10.1145/1132516.1132617

A quasi-PTAS for unsplittable flow on line graphs

Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber

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

94 Scopus citations

Abstract

We study the Unsplittable Flow Problem (UFP) on line graphs and cycles, focusing on the long-standing open question of whether the problem is APX-hard. We describe a deterministic quasi-polynomial time approximation scheme for UFP on line graphs, thereby ruling out an APX-hardness result, unless NP ⊆ DTIME(2^polylog(n)). Our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. We extend this result to undirected cycle graphs. Earlier results on this problem included a polynomial time (2 + ε) -approximation under the assumption that no demand exceeds any edge capacity (the "no-bottleneck assumption") and a superconstant integrality gap if this assumption did not hold. Unlike most earlier work on UFP, our results do not require a no-bottleneck assumption.

Original language	English (US)
Title of host publication	STOC'06
Subtitle of host publication	Proceedings of the 38th Annual ACM Symposium on Theory of Computing
Publisher	Association for Computing Machinery (ACM)
Pages	721-729
Number of pages	9
ISBN (Print)	1595931341, 9781595931344
DOIs	https://doi.org/10.1145/1132516.1132617
State	Published - 2006
Externally published	Yes
Event	38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States Duration: May 21 2006 → May 23 2006

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
Volume	2006
ISSN (Print)	0737-8017

Conference

Conference	38th Annual ACM Symposium on Theory of Computing, STOC'06
Country/Territory	United States
City	Seattle, WA
Period	5/21/06 → 5/23/06

All Science Journal Classification (ASJC) codes

Software

Keywords

Approximation algorithms
Approximation scheme
Resource allocation
Scheduling
Unsplittable flow

Access to Document

10.1145/1132516.1132617

Cite this

Bansal, N., Chakrabarti, A., Epstein, A., & Schieber, B. (2006). A quasi-PTAS for unsplittable flow on line graphs. In STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (pp. 721-729). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 2006). Association for Computing Machinery (ACM). https://doi.org/10.1145/1132516.1132617

@inproceedings{5684eae77408428ea74f87f39878fc4f,

title = "A quasi-PTAS for unsplittable flow on line graphs",

abstract = "We study the Unsplittable Flow Problem (UFP) on line graphs and cycles, focusing on the long-standing open question of whether the problem is APX-hard. We describe a deterministic quasi-polynomial time approximation scheme for UFP on line graphs, thereby ruling out an APX-hardness result, unless NP ⊆ DTIME(2polylog(n)). Our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. We extend this result to undirected cycle graphs. Earlier results on this problem included a polynomial time (2 + ε) -approximation under the assumption that no demand exceeds any edge capacity (the {"}no-bottleneck assumption{"}) and a superconstant integrality gap if this assumption did not hold. Unlike most earlier work on UFP, our results do not require a no-bottleneck assumption.",

keywords = "Approximation algorithms, Approximation scheme, Resource allocation, Scheduling, Unsplittable flow",

author = "Nikhil Bansal and Amit Chakrabarti and Amir Epstein and Baruch Schieber",

year = "2006",

doi = "10.1145/1132516.1132617",

language = "English (US)",

isbn = "1595931341",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery (ACM)",

pages = "721--729",

booktitle = "STOC'06",

address = "United States",

note = "38th Annual ACM Symposium on Theory of Computing, STOC'06 ; Conference date: 21-05-2006 Through 23-05-2006",

}

Bansal, N, Chakrabarti, A, Epstein, A & Schieber, B 2006, A quasi-PTAS for unsplittable flow on line graphs. in STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, vol. 2006, Association for Computing Machinery (ACM), pp. 721-729, 38th Annual ACM Symposium on Theory of Computing, STOC'06, Seattle, WA, United States, 5/21/06. https://doi.org/10.1145/1132516.1132617

A quasi-PTAS for unsplittable flow on line graphs. / Bansal, Nikhil; Chakrabarti, Amit; Epstein, Amir et al.
STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), 2006. p. 721-729 (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 2006).

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

TY - GEN

T1 - A quasi-PTAS for unsplittable flow on line graphs

AU - Bansal, Nikhil

AU - Chakrabarti, Amit

AU - Epstein, Amir

AU - Schieber, Baruch

PY - 2006

Y1 - 2006

N2 - We study the Unsplittable Flow Problem (UFP) on line graphs and cycles, focusing on the long-standing open question of whether the problem is APX-hard. We describe a deterministic quasi-polynomial time approximation scheme for UFP on line graphs, thereby ruling out an APX-hardness result, unless NP ⊆ DTIME(2polylog(n)). Our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. We extend this result to undirected cycle graphs. Earlier results on this problem included a polynomial time (2 + ε) -approximation under the assumption that no demand exceeds any edge capacity (the "no-bottleneck assumption") and a superconstant integrality gap if this assumption did not hold. Unlike most earlier work on UFP, our results do not require a no-bottleneck assumption.

AB - We study the Unsplittable Flow Problem (UFP) on line graphs and cycles, focusing on the long-standing open question of whether the problem is APX-hard. We describe a deterministic quasi-polynomial time approximation scheme for UFP on line graphs, thereby ruling out an APX-hardness result, unless NP ⊆ DTIME(2polylog(n)). Our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. We extend this result to undirected cycle graphs. Earlier results on this problem included a polynomial time (2 + ε) -approximation under the assumption that no demand exceeds any edge capacity (the "no-bottleneck assumption") and a superconstant integrality gap if this assumption did not hold. Unlike most earlier work on UFP, our results do not require a no-bottleneck assumption.

KW - Approximation algorithms

KW - Approximation scheme

KW - Resource allocation

KW - Scheduling

KW - Unsplittable flow

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

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

U2 - 10.1145/1132516.1132617

DO - 10.1145/1132516.1132617

M3 - Conference contribution

AN - SCOPUS:33748093735

SN - 1595931341

SN - 9781595931344

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 721

EP - 729

BT - STOC'06

PB - Association for Computing Machinery (ACM)

T2 - 38th Annual ACM Symposium on Theory of Computing, STOC'06

Y2 - 21 May 2006 through 23 May 2006

ER -

A quasi-PTAS for unsplittable flow on line graphs

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this