11 papers
Load Balancing: The Long Road from Theory to Practice
Sebastian Berndt, Max A. Deppert, Klaus Jansen +1
There is a long history of approximation schemes for the problem of scheduling jobs on identical machines to minimize the makespan. Such a scheme grants a -approximation sol…
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…
Tightness of Sensitivity and Proximity Bounds for Integer Linear Programs
Sebastian Berndt, Klaus Jansen, Alexandra Lassota
We consider ILPs, where each variable corresponds to an integral point within a polytope , i. e., ILPs of the form $\min\{c^{\top}x\mid \sum_{p\in\mathcal P\cap \mathb…
Solving Packing Problems with Few Small Items Using Rainbow Matchings
Max Bannach, Sebastian Berndt, Marten Maack +4
An important area of combinatorial optimization is the study of packing and covering problems, such as Bin Packing, Multiple Knapsack, and Bin Covering. Those problems have been st…
New Bounds for the Vertices of the Integer Hull
Sebastian Berndt, Klaus Jansen, Kim-Manuel Klein
The vertices of the integer hull are the integral equivalent to the well-studied basic feasible solutions of linear programs. In this paper we give new bounds on the number of non-…
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…