@TechReport{Dartmouth:TR2005-561,
  author = {Nikhil Bansal and Amit Chakrabarti and Amir Epstein and Baruch Schieber},
  title = {{A Quasi-PTAS for Unsplittable Flow on Line Graphs}},
  institution = {Dartmouth College, Computer Science},
  address = {Hanover, NH},
  number = {TR2005-561},
  year = {2005},
  month = {October},
  URL = {http://www.cs.dartmouth.edu/reports/TR2005-561.pdf},
  abstract = {
    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.
  }
}