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

 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 + eps for any constant eps>0. This is the best known factor even in the case of uniform edge capacities. 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 + eps)-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 + eps)-approximation algorithm for UFP.

Joint work with Fabrizio Grandoni, Tobias Mömke and Hang Zhou.

Date: Aug 29, 2018 at 13:30 h
Venue: Repúblia 701, Sala 33 (3er piso)
Speaker: Andres Wiese
Affiliation: Universidad de Chile
Coordinator: Mario B.; Andrea J.; José V.

Abstract:
PDF