Seminar: Andreas Wiese (Vrije Universiteit Amsterdam)

In the Unsplittable Flow on a Path problem (UFP) we are given a path with edge capacities, and a set of tasks where each task is characterized by a subpath, a demand, and a weight. The goal is to select a subset of tasks of maximum total weight such that the total demand of the selected tasks using each edge $e$ is at most the capacity of $e$. The problem admits a QPTAS. After a long sequence of improvements, the currently best known polynomial time approximation algorithm for UFP has an approximation ratio of $1+\frac{1}{e+1}+\eps < 1.269$. It has been an open question whether this problem admits a PTAS.
In this talk, we present a polynomial time $(1+\eps)$-approximation algorithm for UFP.