6 papers
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…
A -approximation algorithm for the general scheduling problem in quasipolynomial time
Alexander Armbruster, Lars Rohwedder, Andreas Wiese
We study the general scheduling problem (GSP) which generalizes and unifies several well-studied preemptive single-machine scheduling problems, such as weighted flow time, weighted…
Multiplicative assignment with upgrades
Alexander Armbruster, Lars Rohwedder, Stefan Weltge +2
We study a problem related to submodular function optimization and the exact matching problem for which we show a rather peculiar status: its natural LP-relaxation can have fractio…
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…
Simpler constant factor approximation algorithms for weighted flow time -- now for any -norm
Alexander Armbruster, Lars Rohwedder, Andreas Wiese
A prominent problem in scheduling theory is the weighted flow time problem on one machine. We are given a machine and a set of jobs, each of them characterized by a processing time…
A PTAS for Minimizing Weighted Flow Time on a Single Machine
Alexander Armbruster, Lars Rohwedder, Andreas Wiese
An important objective in scheduling literature is to minimize the sum of weighted flow times. We are given a set of jobs where each job is characterized by a release time, a proce…