5 papers · 1 filter
Convolution and Knapsack in Higher Dimensions
Kilian Grage, Klaus Jansen, Björn Schumacher
In the Knapsack problem, one is given the task of packing a knapsack of a given size with items in order to gain a packing with a high profit value. An important connection to the…
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…
Robust Online Algorithms for Dynamic Choosing Problems
Sebastian Berndt, Kilian Grage, Klaus Jansen +2
Semi-online algorithms that are allowed to perform a bounded amount of repacking achieve guaranteed good worst-case behaviour in a more realistic setting. Most of the previous work…
Robust Online Algorithms for Dynamic Problems
Sebastian Berndt, Valentin Dreismann, Kilian Grage +2
Online algorithms that allow a small amount of migration or recourse have been intensively studied in the last years. They are essential in the design of competitive algorithms for…
An EPTAS for machine scheduling with bag-constraints
Kilian Grage, Klaus Jansen, Kim Manuel Klein
Machine scheduling is a fundamental optimization problem in computer science. The task of scheduling a set of jobs on a given number of machines and minimizing the makespan is well…