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