2024/07/14 by Doron-Arad, Ilan, Grandoni, Fabrizio, Kulik, Ariel
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2407.10138
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/loglog 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.