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…