2025/03/22 by Armbruster, Alexander, Grandoni, Fabrizio, Husić, Edin +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2503.17802
In the Time-Windows Unsplittable Flow on a Path problem (twUFP) we are given a resource whose available amount changes over a given time interval (modeled as the edge-capacities of a given path G) and a collection of tasks. Each task is characterized by a demand (of the considered resource), a profit, an integral processing time, and a time window. Our goal is to compute a maximum profit subset of tasks and schedule them non-preemptively within their respective time windows, such that the total demand of the tasks using each edge e is at most the capacity of e. We prove that twUFP is APX-hard which contrasts the setting of the problem without time windows, i.e., Unsplittable Flow on a Path (UFP), for which a PTAS was recently discovered [Grandoni, Mömke, Wiese, STOC 2022]. Then, we present a quasi-polynomial-time 2+ε approximation for twUFP under resource augmentation. Our approximation ratio improves to 1+ε if all tasks' time windows are identical. Our APX-hardness holds also for this special case and, hence, rules out such a PTAS (and even a QPTAS, unless NP\subseteqDTIME(npoly(log n))) without resource augmentation.