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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\textsf{APX}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">APX</mi> </math></EquationSource> </InlineEquation>-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ömke, Wiese, STOC 2022]. Then, we present a quasi-polynomial-time <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$2+\varepsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mo>+</mo> <mi>ε</mi> </mrow> </math></EquationSource> </InlineEquation> approximation for twUFP under resource augmentation. Our approximation ratio improves to <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$1+\varepsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>+</mo> <mi>ε</mi> </mrow> </math></EquationSource> </InlineEquation> if all tasks’ time windows are identical. Our <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\textsf{APX}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">APX</mi> </math></EquationSource> </InlineEquation>-hardness holds also for this special case and, hence, rules out such a PTAS (and even a QPTAS, unless <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\textsf{NP}\subseteq \textrm{DTIME}(n^{\textrm{poly}(\log n)})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="sans-serif">NP</mi> <mo>⊆</mo> <mtext>DTIME</mtext> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mtext>poly</mtext> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>) without resource augmentation.

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

期刊论文
出版模式：

开放获取
发表日期：

2026年8月4日

查看全文

Alexander Armbruster,
Fabrizio Grandoni,
Edin Husić,
Antoine Tinguely,
Andreas Wiese

摘要

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}$ $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ömke, Wiese, STOC 2022]. Then, we present a quasi-polynomial-time $2+\varepsilon $ $2 + ε$ approximation for twUFP under resource augmentation. Our approximation ratio improves to $1+\varepsilon $ $1 + ε$ if all tasks’ time windows are identical. Our $\textsf{APX}$ $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)})$ $NP \subseteq DTIME (n^{poly (log n)})$ ) without resource augmentation.