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


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)
Number of pages9
ISBN (Print)1595931341, 9781595931344
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
ISSN (Print)0737-8017


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

All Science Journal Classification (ASJC) codes

  • Software


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


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

Cite this