4 papers · 1 filter
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…
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…
The Support of Bin Packing is Exponential
Klaus Jansen, Felix Ohnesorge, Lis Pirotton +1
Consider the classical Bin Packing problem with different item sizes and amounts of items The support of a Bin Packing solution is the number of differently filled…
Improved Algorithms for Monotone Moldable Job Scheduling using Compression and Convolution
Kilian Grage, Klaus Jansen, Felix Ohnesorge
In the moldable job scheduling problem one has to assign a set of jobs to machines, in order to minimize the time it takes to process all jobs. Each job is moldable, so it…