A quasi-PTAS for unsplittable flow on line graphs

Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

92 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(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.

Original languageEnglish (US)
Title of host publicationSTOC'06
Subtitle of host publicationProceedings of the 38th Annual ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery (ACM)
Pages721-729
Number of pages9
ISBN (Print)1595931341, 9781595931344
DOIs
StatePublished - 2006
Externally publishedYes
Event38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States
Duration: May 21 2006May 23 2006

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume2006
ISSN (Print)0737-8017

Conference

Conference38th Annual ACM Symposium on Theory of Computing, STOC'06
Country/TerritoryUnited States
CitySeattle, WA
Period5/21/065/23/06

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Approximation algorithms
  • Approximation scheme
  • Resource allocation
  • Scheduling
  • Unsplittable flow

Fingerprint

Dive into the research topics of 'A quasi-PTAS for unsplittable flow on line graphs'. Together they form a unique fingerprint.

Cite this