33 citations · 53 across the 12 of their papers we have counts for
4 papers · 1 filter
Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering
Carsten Fischer, Heiko Röglin
In the bin covering problem, the goal is to fill as many bins as possible up to a certain minimal level with a given set of items of different sizes. Online variants, in which the…
New Deterministic Algorithms for Solving Parity Games
Matthias Mnich, Heiko Röglin, Clemens Rösner
We study parity games in which one of the two players controls only a small number of nodes and the other player controls the other nodes of the game. Our main result is…
The Alternating Stock Size Problem and the Gasoline Puzzle
Alantha Newman, Heiko Röglin, Johanna Seif
Given a set S of integers whose sum is zero, consider the problem of finding a permutation of these integers such that: (i) all prefix sums of the ordering are nonnegative, and (ii…
Smoothed Analysis of the Successive Shortest Path Algorithm
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey +2
The minimum-cost flow problem is a classic problem in combinatorial optimization with various applications. Several pseudo-polynomial, polynomial, and strongly polynomial algorithm…