19 citations · 38 across the 6 of their papers we have counts for
3 papers · 2 filters
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…
Online Packet Scheduling with Bounded Delay and Lookahead
Martin Böhm, Marek Chrobak, Łukasz Jeż +3
We study the online bounded-delay packet scheduling problem (BDPS), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each pac…
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…