research-article

A logarithmic approximation for unsplittable flow on line graphs

Authors:

Zachary Friggstad,

Rohit Khandekar,

Mohammad R. SalavatipourAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 10, Issue 1

Article No.: 1, Pages 1 - 15

https://doi.org/10.1145/2532645

Published: 01 January 2014 Publication History

Abstract

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 s_i, an end time t_i, a demand d_i > 0, and a profit p_i > 0. A task, if accepted, requires d_i units of “bandwidth” from time s_i to t_i and accrues a profit of p_i. For every time t, we are also specified the available bandwidth c_t, and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints.

We present the first polynomial time O(log n) approximation algorithm for this problem. This significantly advances the state of the art, as no polynomial time o(n) approximation was known previously. Previous results for this problem were known only in more restrictive settings; in particular, either the instance satisfies the so-called “no-bottleneck” assumption: max_i d_i ≤ min_t c_t, or the ratio of both maximum to minimum demands and maximum to minimum capacities are polynomially (or quasi-polynomially) bounded in n. Our result, on the other hand, does not require 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 Ω(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.

References

[1]

M. Andrews, J. Chuzhoy, S. Khanna, and L. Zhang. 2005. Hardness of the undirected edge-disjoint paths problem with congestion. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05). IEEE Computer Society, Washington, DC, 226--244.

Digital Library

[2]

M. Andrews and L. Zhang. 2006. Logarithmic hardness of the undirected edge-disjoint paths problem. J. ACM 53, 745--761.

Digital Library

[3]

A. Arackaparambil, A. Chakrabarti, and C. Huang. 2009. Approximability of unsplittable flow on trees. Dartmouth Technical Report TR2009-642.

[4]

Y. Azar and O. Regev. 2001. Strongly polynomial algorithms for the unsplittable flow problem. In Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization. 15--29.

Digital Library

[5]

N. Bansal, A. Chakrabarti, A. Epstein, and B. Schieber. 2006. A quasi-ptas for unsplittable flow on line graphs. In Proceedings of the 38th Annual ACM Aymposium on Theory of Computing (STOC’06). ACM, New York, NY, 721--729.

Digital Library

[6]

N. Bansal, Z. Friggstad, R. Khandekar, and M. Salavatipour. 2009. A logarithmic approximation for unsplittable flow on line graphs. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’09). Society for Industrial and Applied Mathematics, Philadelphia, PA, 702--709.

Digital Library

[7]

A. Bar-Noy, R. Bar-Yehuda, A. Freund, J. Naor, and B. Schieber. 2001. A unified approach to approximating resource allocation and scheduling. J. ACM 48, 1069--1090.

Digital Library

[8]

A. Baveja and A. Srinivasan. 2000. Approximation algorithms for disjoint paths and related routing and packing problems. Mathematics of Operations Research 25, 2000.

Digital Library

[9]

P. Bonsma, J. Schulz, and A. Wiese. 2011. A constant factor approximation algorithm for unsplittable flow on paths. In FOCS, R. Ostrovsky, Ed. IEEE, 47--56.

Digital Library

[10]

G. Calinescu, A. Chakrabarti, H. Karloff, and Y. Rabani. 2011. An improved approximation algorithm for resource allocation. ACM Trans. Algorithms 7, 48:1--48:7.

Digital Library

[11]

A. Chakrabarti, C. Chekuri, A. Kumar, and A. Gupta. 2002. Approximation algorithms for the unsplittable flow problem. In Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX’02). Springer-Verlag, London, 51--66.

Digital Library

[12]

C. Chekuri, A. Ene, and N. Korula. 2009. Unsplittable flow in paths and trees and column-restricted packing integer programs. In Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX’09/RANDOM’09). Springer-Verlag, Berlin, 42--55.

Digital Library

[13]

C. Chekuri, S. Khanna, and B. Shepherd. 2006. An o(n) approximation and integrality gap for disjoint paths and unsplittable flow. Theory of Computing 2, 2006.

[14]

C. Chekuri, M. Mydlarz, and F. B. Shepherd. 2007. Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms 3.

Digital Library

[15]

S. Fortune, J. Hopcroft, and J. Wyllie. 1978. The Directed Subgraph Homeomorphism Problem. Tech. rep., Ithaca, NY.

Digital Library

[16]

A. Frieze. 2000. Edge-disjoint paths in expander graphs. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’00). Society for Industrial and Applied Mathematics, Philadelphia, PA, 717--725.

Digital Library

[17]

N. Garg, V. Vazirani, and M. Yannakakis. 1997. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18, 3--20.

Digital Library

[18]

V. Guruswami, S. Khanna, R. Rajaraman, B. Shepherd, and M. Yannakakis. 2003. Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67, 473--496.

Digital Library

[19]

O. Ibarra and C. Kim. 1975. Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22, 463--468.

Digital Library

[20]

J. Kleinberg. 1996. Approximation algorithms for disjoint paths problems. Ph.D. thesis, MIT.

Digital Library

[21]

J. Kleinberg and R. Rubinfeld. 1996. Short paths in expander graphs. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Washington, DC, 86.

Digital Library

[22]

P. Kolman and C. Scheideler. 2006. Improved bounds for the unsplittable flow problem. J. Algorithms 61, 20--44.

Digital Library

[23]

A. Phillips, R. Uma, and J. Wein. 2000. Off-line admission control for general scheduling problems. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’00). Society for Industrial and Applied Mathematics, Philadelphia, PA, 879--888.

Digital Library

[24]

A. Srinivasan. 1997. Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Washington, DC, 416.

Digital Library

[25]

V. Vazirani. 2003. Approximation Algorithms. Springer.

Digital Library

Cited By

Sarpatwar KSchieber BShachnai H(2024)The preemptive resource allocation problemJournal of Scheduling10.1007/s10951-023-00786-627:1(103-118)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10951-023-00786-6
Karapetyan AElbassioni KKhonji MChau S(2022)Approximations for generalized unsplittable flow on paths with application to power systems optimizationAnnals of Operations Research10.1007/s10479-022-05054-y320:1(173-204)Online publication date: 7-Nov-2022
https://doi.org/10.1007/s10479-022-05054-y
Hu XKoutris PBlanas SLibkin LPichler RGuagliardo P(2021)Algorithms for a Topology-aware Massively Parallel Computation ModelProceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3452021.3458318(199-214)Online publication date: 20-Jun-2021
https://dl.acm.org/doi/10.1145/3452021.3458318
Show More Cited By

Index Terms

A logarithmic approximation for unsplittable flow on line graphs
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A PTAS for unsplittable flow on a path
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

In the Unsplittable Flow on a Path problem (UFP) we are given a path with edge capacities, and a set of tasks where each task is characterized by a subpath, a demand, and a weight. The goal is to select a subset of tasks of maximum total weight such ...
A quasi-PTAS for unsplittable flow on line graphs
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

We study the Unsplittable Flow Problem (UFP) on line graphs and cycles, focusing on the long-standing open question of whether the problem is APX-hard. We describe a deterministic quasi-polynomial time approximation scheme for UFP on line graphs, ...
How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions

Generalizing many well-known and natural scheduling problems, scheduling with job-specific cost functions has gained a lot of attention recently. In this setting, each job incurs a cost depending on its completion time, given by a private cost function, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 10, Issue 1

January 2014

73 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/2578701

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2014

Accepted: 01 June 2009

Revised: 01 March 2009

Received: 01 February 2007

Published in TALG Volume 10, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Alberta Ingenuity new faculty award
Natural Sciences and Engineering Research Council of Canada
Seventh Framework Programme

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
210
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sarpatwar KSchieber BShachnai H(2024)The preemptive resource allocation problemJournal of Scheduling10.1007/s10951-023-00786-627:1(103-118)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10951-023-00786-6
Karapetyan AElbassioni KKhonji MChau S(2022)Approximations for generalized unsplittable flow on paths with application to power systems optimizationAnnals of Operations Research10.1007/s10479-022-05054-y320:1(173-204)Online publication date: 7-Nov-2022
https://doi.org/10.1007/s10479-022-05054-y
Hu XKoutris PBlanas SLibkin LPichler RGuagliardo P(2021)Algorithms for a Topology-aware Massively Parallel Computation ModelProceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3452021.3458318(199-214)Online publication date: 20-Jun-2021
https://dl.acm.org/doi/10.1145/3452021.3458318
Brubach BSankararaman KSrinivasan AXu P(2019)Algorithms to Approximate Column-sparse Packing ProblemsACM Transactions on Algorithms10.1145/335540016:1(1-32)Online publication date: 15-Nov-2019
https://dl.acm.org/doi/10.1145/3355400
Brubach BSankararaman KSrinivasan AXu PCzumaj A(2018)Algorithms to approximate column-sparse packing problemsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175289(311-330)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175289
Sarpatwar KSchieber BShachnai HScheideler CFineman J(2018)Brief AnnouncementProceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures10.1145/3210377.3210666(343-345)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3210377.3210666
Bar-Yehuda RBeder MRawitz D(2017)A Constant Factor Approximation Algorithm for the Storage Allocation ProblemAlgorithmica10.1007/s00453-016-0137-877:4(1105-1127)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s00453-016-0137-8
Li WLi JGuan LShi Y(2015)The Prize-collecting Call Control Problem on Weighted Lines and RingsRAIRO - Operations Research10.1051/ro/201501050:1(39-46)Online publication date: 26-Aug-2015
https://doi.org/10.1051/ro/2015010

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents