License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.67
URN: urn:nbn:de:0030-drops-146486
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14648/
Martínez-Muñoz, Tomás ;
Wiese, Andreas
FPT and FPT-Approximation Algorithms for Unsplittable Flow on Trees
Abstract
We study the unsplittable flow on trees (UFT) problem in which we are given a tree with capacities on its edges and a set of tasks, where each task is described by a path and a demand. Our goal is to select a subset of the given tasks of maximum size such that the demands of the selected tasks respect the edge capacities. The problem models throughput maximization in tree networks. The best known approximation ratio for (unweighted) UFT is O(log n). We study the problem under the angle of FPT and FPT-approximation algorithms. We prove that
- UFT is FPT if the parameters are the cardinality k of the desired solution and the number of different task demands in the input,
- UFT is FPT under (1+δ)-resource augmentation of the edge capacities for parameters k and 1/δ, and
- UFT admits an FPT-5-approximation algorithm for parameter k. One key to our results is to compute structured hitting sets of the input edges which partition the given tree into O(k) clean components. This allows us to guess important properties of the optimal solution. Also, in some settings we can compute core sets of subsets of tasks out of which at least one task i is contained in the optimal solution. These sets have bounded size, and hence we can guess this task i easily.
A consequence of our results is that the integral multicommodity flow problem on trees is FPT if the parameter is the desired amount of sent flow. Also, even under (1+δ)-resource augmentation UFT is APX-hard, and hence our FPT-approximation algorithm for this setting breaks this boundary.
BibTeX - Entry
@InProceedings{martinezmunoz_et_al:LIPIcs.ESA.2021.67,
author = {Mart{\'\i}nez-Mu\~{n}oz, Tom\'{a}s and Wiese, Andreas},
title = {{FPT and FPT-Approximation Algorithms for Unsplittable Flow on Trees}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {67:1--67:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-204-4},
ISSN = {1868-8969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14648},
URN = {urn:nbn:de:0030-drops-146486},
doi = {10.4230/LIPIcs.ESA.2021.67},
annote = {Keywords: FPT algorithms, FPT-approximation algorithms, packing problems, unsplittable flow, trees}
}
|
Keywords: |
|
FPT algorithms, FPT-approximation algorithms, packing problems, unsplittable flow, trees |
|
Collection: |
|
29th Annual European Symposium on Algorithms (ESA 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
31.08.2021 |
