Unsplittable Flow on a Short Path
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911955097223168 |
|---|---|
| author | Doron-Arad, Ilan Grandoni, Fabrizio Kulik, Ariel |
| author_facet | Doron-Arad, Ilan Grandoni, Fabrizio Kulik, Ariel |
| contents | In the Unsplittable Flow on a Path problem UFP, we are given a path graph with edge capacities and a collection of tasks. Each task is characterized by a demand, a profit, and a subpath. Our goal is to select a maximum profit subset of tasks such that the total demand of the selected tasks that use each edge $e$ is at most the capacity of $e$. Bag-UFP is the generalization of UFP where tasks are partitioned into bags, and we are allowed to select at most one task per bag. UFP admits a PTAS [Grandoni,M{ö}mke,Wiese'22] but not an EPTAS [Wiese'17]. Bag-UFP is APX-hard [Spieksma'99] and the current best approximation is $O(\log n/\log\log n)$ [Grandoni,Ingala,Uniyal'15], where $n$ is the number of tasks.
In this paper, we study the mentioned two problems when parameterized by the number $m$ of edges in the graph, with the goal of designing faster parameterized approximation algorithms. We present a parameterized EPTAS for Bag-UFP, and a substantially faster parameterized EPTAS for UFP (which is an FPTAS for $m=O(1)$). We also show that a parameterized FPTAS for UFP (hence for BagUFP) does not exist, therefore our results are qualitatively tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_10138 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Unsplittable Flow on a Short Path Doron-Arad, Ilan Grandoni, Fabrizio Kulik, Ariel Data Structures and Algorithms In the Unsplittable Flow on a Path problem UFP, we are given a path graph with edge capacities and a collection of tasks. Each task is characterized by a demand, a profit, and a subpath. Our goal is to select a maximum profit subset of tasks such that the total demand of the selected tasks that use each edge $e$ is at most the capacity of $e$. Bag-UFP is the generalization of UFP where tasks are partitioned into bags, and we are allowed to select at most one task per bag. UFP admits a PTAS [Grandoni,M{ö}mke,Wiese'22] but not an EPTAS [Wiese'17]. Bag-UFP is APX-hard [Spieksma'99] and the current best approximation is $O(\log n/\log\log n)$ [Grandoni,Ingala,Uniyal'15], where $n$ is the number of tasks. In this paper, we study the mentioned two problems when parameterized by the number $m$ of edges in the graph, with the goal of designing faster parameterized approximation algorithms. We present a parameterized EPTAS for Bag-UFP, and a substantially faster parameterized EPTAS for UFP (which is an FPTAS for $m=O(1)$). We also show that a parameterized FPTAS for UFP (hence for BagUFP) does not exist, therefore our results are qualitatively tight. |
| title | Unsplittable Flow on a Short Path |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.10138 |