On the Approximability of Unsplittable Flow on a Path with Time Windows
摘要
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 \(\textsf{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+\varepsilon \) approximation for twUFP under resource augmentation. Our approximation ratio improves to \(1+\varepsilon \) if all tasks’ time windows are identical. Our \(\textsf{APX}\) -hardness holds also for this special case and, hence, rules out such a PTAS (and even a QPTAS, unless \(\textsf{NP}\subseteq \textrm{DTIME}(n^{\textrm{poly}(\log n)})\) ) without resource augmentation.