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

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

8 Scopus citations

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 - 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
State	Published - 6 Sep 2022
Externally published	Yes
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

Keywords

approximation
dynamic programming
unsplittable flow

Access to Document

10.1145/3519935.3519959

Cite this

@inproceedings{af79ccf870ac4b7d817f58ea3a10053f,

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 = "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 = sep,

day = "6",

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 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing",

}

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 › peer-review

TY - GEN

T1 - A PTAS for unsplittable flow on a path

AU - Grandoni, Fabrizio

AU - Mömke, Tobias

AU - Wiese, Andreas

PY - 2022/9/6

Y1 - 2022/9/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

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 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

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

Keywords

Access to Document

Other files and links

Fingerprint

Cite this