A logarithmic approximation for unsplittable flow on line graphs

N. Bansal, Z. Friggstad, R. Khandekar, M.R. Salavatipour

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    48 Citations (Scopus)


    We consider the unsplittable flow problem on a line. In this problem, we are given a set of n tasks, each specified by a start time si, an end time ti, a demand di > 0, and a profit pi > 0. A task, if accepted, requires di units of "bandwidth" from time si to ti and accrues a profit of pi. For every time t, we are also specified the available bandwidth ct, and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints. In this paper, we present the first polynomial-time O(log n)-approximation algorithm for this problem. No polynomial-time o(n)-approximation was known prior to this work. Previous results for this problem were known only in more restrictive settings, in particular, either if the given instance satisfies the so-called "no-bottleneck" assumption: maxi di = mint ct, or else if the ratio of the maximum to the minimum demands and ratio of the maximum to the minimum capacities are polynomially (or quasi-polynomially) bounded in n. Our result, on the other hand, does not require any of these assumptions. Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an O(n) integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.
    Original languageEnglish
    Title of host publicationProceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'09, New York NY, USA, January 4-6, 2009)
    EditorsC. Mathieu
    Place of PublicationNew York
    PublisherAssociation for Computing Machinery, Inc
    Publication statusPublished - 2009


    Dive into the research topics of 'A logarithmic approximation for unsplittable flow on line graphs'. Together they form a unique fingerprint.

    Cite this