Fixed-parameter algorithms for Unsplittable Flow Cover

We are given a path with a demand on each edge and a set of tasks, each task being defined by a subpath and a size. The goal is to select a subset of the tasks of minimum cardinality such that on each edge e the total size of the selected tasks using e is at least the demand of e.
There is a polynomial time 4-approximation for the problem [Bar-Noy et al., STOC 2000] and also a QPTAS [Höhn et al., ICALP 2014].
In this paper we study fixed-parameter algorithms for the problem.
We show that it is W[1]-hard but it becomes FPT if we can slighly violate the edge demands (resource augmentation) and also if there are at most k different task sizes.
Then we present a parameterized approximation scheme (PAS), i.e., an algorithm with a running time of f(k)n^{O_{\epsilon}(1)} that outputs a solution with at most (1+\epsilon)k tasks or assert that there is no solution with at most k tasks.
In this algorithm we use a new trick that intuitively allows us to pretend that we can select tasks from OPT multiple times.

Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.