CS Forum: Tobias Mömke, Saarland University "A (5/3 + epsilon)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes"

A (5/3 + epsilon)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes

Tobias Mömke
Saarland University

Abstract:

In the Unsplittable Flow on a Path problem (UFP) we are given a path with edge capacities and a collection of tasks. Each task is characterized by a subpath, a profit, and a demand. Our goal is to compute a maximum profit subset of tasks such that, for each edge e, the
total demand of selected tasks that use e does not exceed the capacity of e. The current best polynomial-time approximation factor for this problem is 2 + epsilon for any constant epsilon > 0 [Anagostopoulos et al.-SODA 2014]. This is the best known factor even in the case of uniform edge capacities [Călinescu et al.-IPCO 2002, TALG 2011]. These results, likewise most prior work, are based on a partition of tasks into large and small depending on their ratio of demand to capacity over their respective edges: these algorithms invoke (1 + epsilon)-approximations for large and small tasks separately.

The known techniques do not seem to be able to combine a big fraction of large and small tasks together (apart from some special cases and quasi-polynomial-time algorithms). The main contribution of this paper is to overcome this critical barrier. Namely, we present a
polynomial-time algorithm that obtains roughly all profit from the optimal large tasks plus one third of the profit from the  optimal small tasks. In combination with known results, this implies a polynomial-time (5/3 + epsilon)-approximation algorithm for UFP.

Our algorithm is based on two main ingredients. First, we prove that there exist certain sub-optimal solutions where, roughly speaking, small tasks are packed into boxes. To prove that such solutions can yield high profit we introduce a horizontal slicing lemma which yields a novel geometric interpretation of certain solutions. The resulting boxed
structure has polynomial complexity, hence cannot be guessed directly. Therefore, our second contribution is a dynamic program that guesses this structure (plus a packing of large and small tasks) on the fly, while losing at most one third of the profit of the remaining small tasks.

(this is joint work with Fabrizio Grandoni, Andreas Wiese, and Hang Zhou; it appeard at STOC 2018)

Host:

Professor Parinya Chalermsook
Department of Computer Science, Aalto University

CS forum is a seminar series arranged at the CS department. The talks are intended for presentations of postdoctoral level researchers and professors, both for visiting and CS-department-based researchers.