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

}