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 -