A quasi-PTAS for unsplittable flow on line graphs

Nikhil Bansal; Amit Chakrabarti; Amir Epstein; Baruch Schieber

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

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
Pages	721-729
Number of pages	9
State	Published - Sep 5 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

Cite this

@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",

month = sep,

day = "5",

language = "English (US)",

isbn = "1595931341",

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

pages = "721--729",

booktitle = "STOC'06",

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, pp. 721-729, 38th Annual ACM Symposium on Theory of Computing, STOC'06, Seattle, WA, United States, 5/21/06.

A quasi-PTAS for unsplittable flow on line graphs. / Bansal, Nikhil; Chakrabarti, Amit; Epstein, Amir; Schieber, Baruch.

STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. 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/9/5

Y1 - 2006/9/5

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

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

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

Other files and links

Fingerprint

Cite this