3 papers
cs.DS2021
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…
cs.DS2019
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…
cs.DS2018
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…