3 papers
cs.DS2026
Improved Approximation Algorithms for Parallel Task Scheduling and Multiple Cluster Scheduling
Bennet Edler, Klaus Jansen, Felix Ohnesorge +1
In the problem of Parallel Task Scheduling (PTS), we are asked to schedule jobs, each with a fixed processing time and machine requirement, such that the completion time of the…
cs.CC2026
A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
Klaus Jansen, Felix Ohnesorge, Lis Pirotton
Consider a high-multiplicity Bin Packing instance with distinct item types. In 2014, Goemans and Rothvoss gave an algorithm with runtime for this problem…
cs.DS2026
A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling
Klaus Jansen, Felix Ohnesorge
In moldable job scheduling, we are provided identical machines and jobs that can be executed on a variable number of machines. The execution time of each job depends on the…