14 citations · 21 across the 20 of their papers we have counts for
5 papers · 1 filter
Better Trees for Santa Claus
Étienne Bamas, Lars Rohwedder
We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes…
On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs
Kim-Manuel Klein, Adam Polak, Lars Rohwedder
The starting point of this paper is the problem of scheduling jobs with processing times and due dates on a single machine so as to minimize the total processing time of tardy…
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…
Flow Time Scheduling and Prefix Beck-Fiala
Nikhil Bansal, Lars Rohwedder, Ola Svensson
We relate discrepancy theory with the classic scheduling problems of minimizing max flow time and total flow time on unrelated machines. Specifically, we give a general reduction t…
Cardinality Constrained Scheduling in Online Models
Leah Epstein, Alexandra Lassota, Asaf Levin +2
Makespan minimization on parallel identical machines is a classical and intensively studied problem in scheduling, and a classic example for online algorithm analysis with Graham's…