A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths

Paul Bonsma, Jens Schulz, Andreas Wiese

    Research output: Contribution to journalArticleAcademicpeer-review

    33 Citations (Scopus)

    Abstract

    In the unsplittable flow problem on a path, we are given a capacitated path $P$ and $n$ tasks, each task having a demand, a profit, and start and end vertices. The goal is to compute a maximum profit set of tasks such that, for each edge $e$ of $P$, the total demand of selected tasks that use $e$ does not exceed the capacity of $e$. This is a well-studied problem that has been described under alternative names, such as resource allocation, bandwidth allocation, resource constrained scheduling, temporal knapsack, and interval packing. We present a polynomial time constant-factor approximation algorithm for this problem. This improves on the previous best known approximation ratio of $O(\log n)$. The approximation ratio of our algorithm is $7+\epsilon$ for any $\epsilon>0$. We introduce several novel algorithmic techniques, which might be of independent interest: a framework which reduces the problem to instances with a bounded range of capacities, and a new geometrically inspired dynamic program which solves to optimality a special case of the problem of finding a maximum weight independent set of rectangles. In the setting of resource augmentation, wherein the capacities can be slightly violated, we give a $(2+\epsilon)$-approximation algorithm. In addition, we show that the problem is strongly NP-hard even if all edge capacities are equal and all demands are either 1, 2, or 3.
    Original languageEnglish
    Pages (from-to)767-799
    Number of pages33
    JournalSIAM journal on computing
    Volume43
    Issue number2
    DOIs
    Publication statusPublished - 29 Apr 2014

    Keywords

    • MSC-68R05
    • MSC-68W25
    • Resource allocation
    • Strong NP-hardness
    • Constant-factor approximation
    • Maximum weight independent set
    • Unsplittable flow
    • n/a OA procedure

    Fingerprint

    Dive into the research topics of 'A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths'. Together they form a unique fingerprint.

    Cite this