A PTAS for unsplittable flow on a path

Fabrizio Grandoni; Tobias Mömke; Andreas Wiese

doi:10.1145/3519935.3519959

A PTAS for unsplittable flow on a path

Fabrizio Grandoni, Tobias Mömke, Andreas Wiese

Operations Analytics

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

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 that the total demand of the selected tasks using each edge e is at most the capacity of e. The problem admits a QPTAS [Bansal, Chakrabarti, Epstein, Schieber, STOC'06; Batra, Garg, Kumar, Mömke, Wiese, SODA'15]. After a long sequence of improvements [Bansal, Friggstad, Khandekar, Salavatipour, SODA'09; Bonsma, Schulz, Wiese, FOCS'11; Anagnostopoulos, Grandoni, Leonardi, Wiese, SODA'14; Grandoni, Mömke, Wiese, Zhou, STOC'18], the best known polynomial time approximation algorithm for UFP has an approximation ratio of 1+1/(e+1) + epsilon < 1.269 [Grandoni, Mömke, Wiese, SODA'22]. It has been an open question whether this problem admits a PTAS. In this paper, we solve this open question and present a polynomial time (1 + epsilon)-approximation algorithm for UFP.

Original language	English
Title of host publication	STOC 2022
Subtitle of host publication	Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
Editors	Stefano Leonardi, Anupam Gupta
Publisher	Association for Computing Machinery
Pages	289-302
Number of pages	14
ISBN (Electronic)	9781450392648
DOIs	https://doi.org/10.1145/3519935.3519959
Publication status	Published - Jun 2022
Event	54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 - Rome, Italy Duration: 20 Jun 2022 → 24 Jun 2022

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Conference

Conference	54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022
Country/Territory	Italy
City	Rome
Period	20/06/22 → 24/06/22

Bibliographical note

Funding Information:
∗Partially supported by the SNSF Excellence Grant 200020B_182865/1. †Partially supported by DFG Grant 439522729 (Heisenberg-Grant) and DFG Grant 439637648 (Sachbeihilfe) ‡Partially supported by ANID Fondecyt Regular grant 1200173.

Publisher Copyright:
© 2022 ACM.

Funding

∗Partially supported by the SNSF Excellence Grant 200020B_182865/1. †Partially supported by DFG Grant 439522729 (Heisenberg-Grant) and DFG Grant 439637648 (Sachbeihilfe) ‡Partially supported by ANID Fondecyt Regular grant 1200173.

Keywords

approximation
dynamic programming
unsplittable flow

Access to Document

10.1145/3519935.3519959

Persistent URL (handle)

Persistent link

Cite this

@inproceedings{a4072292fc554cc1ac6723b028ed9571,

title = "A PTAS for unsplittable flow on a path",

abstract = "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 that the total demand of the selected tasks using each edge e is at most the capacity of e. The problem admits a QPTAS [Bansal, Chakrabarti, Epstein, Schieber, STOC'06; Batra, Garg, Kumar, M{\"o}mke, Wiese, SODA'15]. After a long sequence of improvements [Bansal, Friggstad, Khandekar, Salavatipour, SODA'09; Bonsma, Schulz, Wiese, FOCS'11; Anagnostopoulos, Grandoni, Leonardi, Wiese, SODA'14; Grandoni, M{\"o}mke, Wiese, Zhou, STOC'18], the best known polynomial time approximation algorithm for UFP has an approximation ratio of 1+1/(e+1) + epsilon < 1.269 [Grandoni, M{\"o}mke, Wiese, SODA'22]. It has been an open question whether this problem admits a PTAS. In this paper, we solve this open question and present a polynomial time (1 + epsilon)-approximation algorithm for UFP.",

keywords = "approximation, dynamic programming, unsplittable flow",

author = "Fabrizio Grandoni and Tobias M{\"o}mke and Andreas Wiese",

note = "Funding Information: ∗Partially supported by the SNSF Excellence Grant 200020B_182865/1. †Partially supported by DFG Grant 439522729 (Heisenberg-Grant) and DFG Grant 439637648 (Sachbeihilfe) ‡Partially supported by ANID Fondecyt Regular grant 1200173. Publisher Copyright: {\textcopyright} 2022 ACM.; 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 ; Conference date: 20-06-2022 Through 24-06-2022",

year = "2022",

month = jun,

doi = "10.1145/3519935.3519959",

language = "English",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "289--302",

editor = "Stefano Leonardi and Anupam Gupta",

booktitle = "STOC 2022",

}

Grandoni, F, Mömke, T & Wiese, A 2022, A PTAS for unsplittable flow on a path. in S Leonardi & A Gupta (eds), STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 289-302, 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, Rome, Italy, 20/06/22. https://doi.org/10.1145/3519935.3519959

A PTAS for unsplittable flow on a path. / Grandoni, Fabrizio; Mömke, Tobias; Wiese, Andreas.
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. ed. / Stefano Leonardi; Anupam Gupta. Association for Computing Machinery, 2022. p. 289-302 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A PTAS for unsplittable flow on a path

AU - Grandoni, Fabrizio

AU - Mömke, Tobias

AU - Wiese, Andreas

N1 - Funding Information: ∗Partially supported by the SNSF Excellence Grant 200020B_182865/1. †Partially supported by DFG Grant 439522729 (Heisenberg-Grant) and DFG Grant 439637648 (Sachbeihilfe) ‡Partially supported by ANID Fondecyt Regular grant 1200173. Publisher Copyright: © 2022 ACM.

PY - 2022/6

Y1 - 2022/6

N2 - 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 that the total demand of the selected tasks using each edge e is at most the capacity of e. The problem admits a QPTAS [Bansal, Chakrabarti, Epstein, Schieber, STOC'06; Batra, Garg, Kumar, Mömke, Wiese, SODA'15]. After a long sequence of improvements [Bansal, Friggstad, Khandekar, Salavatipour, SODA'09; Bonsma, Schulz, Wiese, FOCS'11; Anagnostopoulos, Grandoni, Leonardi, Wiese, SODA'14; Grandoni, Mömke, Wiese, Zhou, STOC'18], the best known polynomial time approximation algorithm for UFP has an approximation ratio of 1+1/(e+1) + epsilon < 1.269 [Grandoni, Mömke, Wiese, SODA'22]. It has been an open question whether this problem admits a PTAS. In this paper, we solve this open question and present a polynomial time (1 + epsilon)-approximation algorithm for UFP.

AB - 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 that the total demand of the selected tasks using each edge e is at most the capacity of e. The problem admits a QPTAS [Bansal, Chakrabarti, Epstein, Schieber, STOC'06; Batra, Garg, Kumar, Mömke, Wiese, SODA'15]. After a long sequence of improvements [Bansal, Friggstad, Khandekar, Salavatipour, SODA'09; Bonsma, Schulz, Wiese, FOCS'11; Anagnostopoulos, Grandoni, Leonardi, Wiese, SODA'14; Grandoni, Mömke, Wiese, Zhou, STOC'18], the best known polynomial time approximation algorithm for UFP has an approximation ratio of 1+1/(e+1) + epsilon < 1.269 [Grandoni, Mömke, Wiese, SODA'22]. It has been an open question whether this problem admits a PTAS. In this paper, we solve this open question and present a polynomial time (1 + epsilon)-approximation algorithm for UFP.

KW - approximation

KW - dynamic programming

KW - unsplittable flow

UR - http://www.scopus.com/inward/record.url?scp=85132786040&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85132786040&partnerID=8YFLogxK

U2 - 10.1145/3519935.3519959

DO - 10.1145/3519935.3519959

M3 - Conference contribution

AN - SCOPUS:85132786040

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 289

EP - 302

BT - STOC 2022

A2 - Leonardi, Stefano

A2 - Gupta, Anupam

PB - Association for Computing Machinery

T2 - 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022

Y2 - 20 June 2022 through 24 June 2022

ER -

A PTAS for unsplittable flow on a path

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this