Showing 2024Show all
2 papers · 1 filter
cs.DS2024
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…
cs.DS2024
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…