May 16, 2006 - Amir Epstein

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 $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.