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 \(\mathrm{NP} ceq \mathrm{DTIME}(2^{polylog(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+eps)\)-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.
This is a joint work with Nikhil Bansal, Amit Chakrabarti and Baruch Schieber.