%T A Quasi-PTAS for Unsplittable Flow on Line Graphs
%A Nikhil Bansal
%A Amit Chakrabarti
%A Amir Epstein
%A Baruch Schieber
%R Technical Report TR2005-561
%I Dartmouth College, Computer Science
%C Hanover, NH
%D October 2005
%U http://www.cs.dartmouth.edu/reports/TR2005-561.pdf
%X
 We study the Unsplittable Flow Problem (UFP) on a line graph, 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 is contained in DTIME(2^polylog(n)). Our result
 requires a quasi-polynomial bound on all edge capacities and demands in
 the input instance.
 	Earlier results on this problem included a polynomial time
 (2+epsilon)-approximation under the assumption that no demand exceeds any
 edge capacity (the "no-bottleneck assumption") and a super-constant
 integrality gap if this assumption did not hold. Unlike most earlier
 work on UFP, our results do not require a no-bottleneck assumption.