Logarithmic price of buffer downscaling on line metrics

Abstrakt

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 performs worse by a factor of Omega(logn) than an offline algorithm with buffer k.

In particular, this demonstrates that the O(logn)-competitive online algorithm MOVINGPARTITION by Gamzu and Segev (2009) [9] is essentially optimal against any offline algorithm with a slightly larger buffer.

Klíčová slova

• Reordering buffer
• Competitive analysis