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 -