On the Approximability of Unsplittable Flow on a Path with Time Windows
Alexander Armbruster, Fabrizio Grandoni, Edin Husić, Antoine Tinguely, Andreas Wiese · 2025
Read On the Approximability of Unsplittable Flow on a Path with Time Windows by Alexander Armbruster, Fabrizio Grandoni, Edin Husić, Antoine Tinguely, Andreas Wiese (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-17802.txt.
Introduction
Alexander Armbruster and co-authors settle how well a scheduling problem with time windows can be approximated. Tasks bid for a resource whose supply varies along a path over time. Each task brings a demand, a profit, a fixed runtime, and a window it must fit inside. The goal is the most profitable feasible schedule, with no task split. Without time windows, the sibling problem recently gained a near-perfect approximation scheme. Windows change everything.
The team proves the windowed version is APX-hard, ruling out such a scheme. Even identical windows stay hard. With resource augmentation, extra supply to lean on, a quasi-polynomial algorithm reaches within a small factor of optimal. Identical windows tighten the guarantee further. The paper draws the exact line where windows defeat approximation.
Catalog record
| CREATOR | Alexander Armbruster, Fabrizio Grandoni, Edin Husić, Antoine Tinguely, Andreas Wiese |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-17802
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Approximability of Unsplittable Flow on a Path with Time Windows Thanks: Fabrizio Grandoni, Edin Husić and Antoine Tinguely were supported by the Swiss National Science Foundation (SNSF) Grant 200021 200731/1. Alexander Armbruster, Fabrizio Grandoni, Edin Husić, Antoine Tinguely, Andreas Wiese Abstract 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 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 e is at most the capacity of e e . We prove that twUFP is 𝖠𝖯𝖷 \mathsf{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 + ε 2+\varepsilon approximation for twUFP under resource augmentation. Our approximation ratio improves to 1 + ε 1+\varepsilon if all tasks’ time windows are identical. Our 𝖠𝖯𝖷 \mathsf{APX} -hardness holds also for this special case and, hence, rules out such a PTAS (and even a QPTAS, unless 𝖭𝖯 ⊆ DTIME ( n poly ( log n ) ) \mathsf{NP}\subseteq\mathrm{DTIME}(n^{\mathrm{poly}(\log n)}) ) without resource augmentation. 1 Introduction In the well-studied Unsplittable Flow on a Path problem ( UFP ), we are given a path graph G=(V,E) with m edges, a capacity u(e)\in\mathbb{N} for each edge e\in E , and a collection T of n tasks. Each task i\in T is characterized by a weight (or profit ) w(i)\in\mathbb{N} , a demand d(i)\in\mathbb{N} , and a subpath P(i)\subseteq E of G . 1 1 1 Given a subpath P of G , we will sometimes use P also to denote the corresponding set of edges E(P) . The meaning will be clear from the context. A feasible solution consists of a subset of tasks S\subseteq T such that \sum_{i\in S:e\in P(i)}d(i)\leq u(e) for each e\in E . In other words, the total demand of the tasks in S whose subpath contains e does not exceed the capacity of e . Our goal is to compute a feasible solution \mathsf{OPT} of maximum profit w(\mathsf{OPT})\coloneqq\sum_{i\in\mathsf{OPT}}w(i) . One can naturally interpret G as a time interval subdivided into time slots (the edges). At each time slot, a given amount of a considered resource (e.g., energy) is available. Each task i corresponds to a job that we can execute (or not) in a fixed time interval: if i is executed, it consumes a fixed amount of the considered resource during its entire execution and generates a profit of w(i) . UFP is strongly NP-hard [ 8 , 11 ] , and a lot of attention was devoted to the design of approximation algorithms for it [ 1 , 2 , 3 , 6 , 8 , 16 , 18 , 19 , 20 ] , culminating in a recent PTAS for the problem [ 17 ] . In UFP , we have no flexibility for the time interval during which each selected task i is executed. In practice, it makes sense to consider scenarios where i has a given length (or processing time) and a time window during which it needs to be executed. In this setting, for each selected task i we need to specify a starting time for i such that i is processed completely within its time window. This leads to the Time-Windows UFP problem ( twUFP ). Here, we are given the same input as in UFP , with the difference that for each task i , instead of a subpath P(i) we are given a length (or processing time ) p(i)\in\{1,\ldots,m\} , and a subpath \tw(i)\subseteq E with at least p(i) edges (the time window of i ). A scheduling of i is a subpath P(i)\subseteq\tw(i) containing precisely p(i) edges. A feasible solution for the given instance is a pair (S,P(\cdot)) such that for each i\in S the path P(i) is a feasible scheduling of i and \sum_{i\in S:e\in P(i)}d(i)\leq u(e) for each e\in E . Our goal is to maximize w(S) , like in UFP . Observe that UFP is the special case of twUFP where for each task i\in T the time window \tw(i) contains exactly p(i) edges; hence, twUFP is strongly \mathsf{NP} -hard. The best known approximation algorithm for it is a O(\log n/\log\log n) -approximation [ 15 ] , improving on a prior result in [ 9 ] (both results hold for a more general problem, bagUFP , which is defined later). However, no result in the literature excludes the existence of a much better approximation ratio for twUFP , including possibly a PTAS. In this paper, we make progress on a better understanding of the approximability of twUFP . 1.1 Our Results and Techniques Our first main result is that twUFP does not admit a PTAS, which in particular implies that it is strictly harder than UFP (unless \mathsf{P=NP} ). We show that this already holds when the time window of each task spans all the edges of G , i.e., if \tw(i)=E for each i\in T ; we denote this special case of the problem by Spanning UFP ( spanUFP ). Our result even holds in the cardinality setting, i.e., when all tasks have unit weight, and for polynomially bounded input data. Theorem 1 . spanUFP (thus also twUFP ) is \mathsf{APX} -hard and does not admit a (polynomial-time) \frac{2755}{2754} -approximation algorithm (unless \mathsf{P=NP} ), even in the cardinality case and if demands and the number of edges is polynomially bounded in n . The proof of Theorem 1 follows from a reduction to Maximum 3-Dimensional Matching (3-DM) and the bound in [ 10 ] . In our reduction, we model 3-DM instances as instances of spanUFP in which the capacity profile models bins (see Figure 1 ), reminiscent of the 2-Dimensional Vector Bin Packing (2-VBP) problem, and adapt the construction in [ 28 ] (which refutes the existence of an asymptotic PTAS for 2-VBP). 0 capacity \cdots Figure 1 : The capacity profile (red) of an instance used in our hardness result for spanUFP . Our second main contribution is a constant factor approximation algorithm for twUFP with resource augmentation which runs in quasi-polynomial time. More specifically, for any constant \varepsilon>0 , we compute a (2+\varepsilon) -approximate solution in time 2^{O_{\varepsilon}(\poly(\log(nm)))} which violates the edge capacities at most by a factor 1+O(\varepsilon) . As usual in the setting of resource augmentation, the approximation ratio is computed with respect to an optimal solution which is not allowed to violate the edge capacities. Theorem 2 . For any \varepsilon>0 , there is a (2+\varepsilon) -approximation for twUFP under (1+O(\varepsilon)) -resource augmentation with running time O\big((mn)^{O(\log^{2}n\log^{5}m/\varepsilon^{4})}\cdot\log U\big) , where U\coloneqq\max_{e\in E}u(e) is the maximum capacity of the instance. For the special case of spanUFP , the approximation ratio of our algorithm