Logarithmic price of buffer downscaling on line metrics

We consider the reordering buffer problem on a line consisting of n equidistant points. We show that, for any constant δ, an (offline) algorithm that has a buffer (1−δ)⋅k performs worse by a factor of Ω(log⁡n) than an offline algorithm with buffer k. In particular, this demonstrates that the O(log⁡n)-competitive online algorithm MovingPartition by Gamzu and Segev (2009) [9] is essentially optimal against any offline algorithm with a slightly larger buffer.