Unsplittable Flow on a Short Path
<|reference_start|>Unsplittable Flow on a Short Path: 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{\"o}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.<|reference_end|>
@article{doron-arad2024unsplittable,
    title={Unsplittable Flow on a Short Path},
    author={Ilan Doron-Arad, Fabrizio Grandoni and Ariel Kulik},
    journal={arXiv preprint arXiv:2407.10138},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.10138},
    primaryClass={cs.DS}
}