5 papers
Scheduling on a Stochastic Number of Machines
Moritz Buchem, Franziska Eberle, Hugo Kooki Kasuya Rosado +2
We consider a new scheduling problem on parallel identical machines in which the number of machines is initially not known, but it follows a given probability distribution. Only af…
Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
Moritz Buchem, Paul Deuker, Andreas Wiese
An important goal in algorithm design is determining the best running time for solving a problem (approximately). For some problems, we know the optimal running time, assuming cert…
A -approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds
Moritz Buchem, Katja Ettmayr, Hugo Kooki Kasuya Rosado +1
For a given set of points in a metric space and an integer , we seek to partition the given points into clusters. For each computed cluster, one typically defines one point…
Scheduling with Machine Conflicts
Moritz Buchem, Linda Kleist, Daniel Schmidt genannt Waldschmidt
We study the scheduling problem of makespan minimization while taking machine conflicts into account. Machine conflicts arise in various settings, e.g., shared resources for pre- a…
Additive Approximation Schemes for Load Balancing Problems
Moritz Buchem, Lars Rohwedder, Tjark Vredeveld +1
In this paper we introduce the concept of additive approximation schemes and apply it to load balancing problems. Additive approximation schemes aim to find a solution with an abso…