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

CREATORAlexander Armbruster, Fabrizio Grandoni, Edin Husić, Antoine Tinguely, Andreas Wiese
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text