EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

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

Mathematical Programming · 04.08.2026

DOI: 10.1007/s10107-026-02408-3 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 04.08.2026. Verfasst von Alexander Armbruster und 4 weiteren Autor:innen. Die Arbeit nennt 47 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung, Deutsche Forschungsgemeinschaft.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 ⊆ DTIME ( n poly ( log n ) ) ) without resource augmentation.

Förderung

  • Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
  • Deutsche Forschungsgemeinschaft

Zitieren

APA

Armbruster, A., Grandoni, F., Husić, E., Tinguely, A., & Wiese, A. (2026). On the approximability of unsplittable flow on a path with time windows. Mathematical Programming. https://doi.org/10.1007/s10107-026-02408-3

Vancouver

Armbruster A, Grandoni F, Husić E, Tinguely A, Wiese A. On the approximability of unsplittable flow on a path with time windows. Mathematical Programming. 2026. doi:10.1007/s10107-026-02408-3

BibTeX
@article{Armbruster2026,
  author = {Armbruster, Alexander and Grandoni, Fabrizio and Husić, Edin and Tinguely, Antoine and Wiese, Andreas},
  title = {On the approximability of unsplittable flow on a path with time windows},
  journal = {Mathematical Programming},
  year = {2026},
  doi = {10.1007/s10107-026-02408-3}
}
Kostenlos starten →