On the approximability of unsplittable flow on a path with time windows

• 成果类型: Article; Early Access
• 署名作者: Armbruster, Alexander; Grandoni, Fabrizio; Husic, Edin; Tinguely, Antoine; Wiese, Andreas
• 署名单位: Technical University of Munich; Universita della Svizzera Italiana
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02408-3
• 发表日期: 2026-08-04
• 关键词: approximation algorithms; Scheduling; APX-hardness; Combinatorial Optimization; resource-allocation; approximation scheme; MULTIPLE MACHINES; Throughput; algorithms; optimization; complexity

摘要

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, for which a PTAS was recently discovered [Grandoni, M & ouml;mke, Wiese, STOC 2022]. Then, we present a quasi-polynomial-time 2+epsilon approximation for twUFP under resource augmentation. Our approximation ratio improves to 1+epsilon 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 subset of DTIME(npoly(logn)) ) without resource augmentation.