2 citations · 4 across the 7 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016
Logarithmic price of buffer downscaling on line metrics
Marcin Bienkowski, Martin Böhm, Łukasz Jeż +5
We consider the reordering buffer problem on a line consisting of n equidistant points. We show that, for any constant delta, an (offline) algorithm that has a buffer (1-delta) k p…
cs.CC2016
Online Chromatic Number is PSPACE-Complete
Martin Böhm, Pavel Veselý
In the online graph coloring problem, vertices from a graph G, known in advance, arrive in an online fashion and an algorithm must immediately assign a color to each incoming verte…
cs.DS2016
A Two-Phase Algorithm for Bin Stretching with Stretching Factor 1.5
Martin Böhm, Jiří Sgall, Rob van Stee +1
Online Bin Stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack t…