3 citations · 3 across the 4 of their papers we have counts for
9 papers · 1 filter
New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines
Sebastian Berndt, Hauke Brinkop, Klaus Jansen +2
Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs d…
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…
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…