3 papers
cs.DS2026
Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely +1
The (Non-Preemptive) Throughput Maximization problem is a natural and fundamental scheduling problem. We are given jobs, where each job is characterized by a processing tim…
cs.DS2025
On the Approximability of Unsplittable Flow on a Path with Time Windows
Alexander Armbruster, Fabrizio Grandoni, Edin Husić +2
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…
cs.DS2024
Unsplittable Flow on a Short Path
Ilan Doron-Arad, Fabrizio Grandoni, Ariel Kulik
In the Unsplittable Flow on a Path problem UFP, we are given a path graph with edge capacities and a collection of tasks. Each task is characterized by a demand, a profit, and a su…