Logarithmic price of buffer downscaling
on line metrics∗
Marcin Bienkowski1 , Martin Böhm2 , Łukasz Jeż1 , Paweł Laskoś-Grabowski1,3 ,
Jan Marcinkowski1 , Jiřı́ Sgall2 , Aleksandra Spyra1 , and Pavel Veselý2
1

arXiv:1610.04915v3 [cs.DS] 22 Jul 2017

2

Institute of Computer Science, University of Wrocław, Poland
Computer Science Institute, Charles University, Czech Republic
3
Electron (Chaddenwych Services Ltd.), London, UK

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 (ACM Trans. on Algorithms, 6(1), 2009) is essentially
optimal against any offline algorithm with a slightly larger buffer.

1 Introduction
In the reordering buffer problem, requests arrive in an online fashion at the points of a metric
space and have to be served by an algorithm. An algorithm has a single server kept at a point
of the metric space and is equipped with a finite buffer, whose capacity is denoted by k. The
buffer is used to give the algorithm a possibility of serving requests in a different order. Namely,
at any time, there can be at most k unprocessed requests, and once their number is exactly k, the
algorithm has to move its server to the position of a pending request of its choice. The request is
then considered served and removed from the buffer. The goal is to minimize the total distance
traveled by the server.
The problem was coined by Räcke et al. [RSW02] and the currently best algorithm for general
metric spaces is a randomized O(log n · log k)-competitive strategy [ERW10, ER17], where n is the
number of points in a metric space. Most of the research focused however on specific metric
spaces, such as uniform metrics [RSW02, AR13, EW05], stars [ACER11, AIMR15, AR10] or lines
of n equidistant points [GS09, KP10].

1.1 Two-stage approach
One of the straightforward ways to attack the problem is by a two-stage approach: (i) compare
an online algorithm to an optimal offline algorithm that has a smaller buffer h < k and (ii) bound
the ratio between optimal offline algorithms equipped with buffers h and k. Such an approach was
successfully executed by Englert and Westermann [EW05] for uniform metrics. They constructed
∗

This work was partially supported by Polish National Science Centre grant 2016/22/E/ST6/00499, by the Center of
Excellence – ITI, project P202/12/G061 of GA ČR (J. Sgall), and by the project 634217 of GAUK (M. Böhm, P. Veselý).

1

an online algorithm Map (with a buffer k) that is 4-competitive against Opt(k/4), where Opt(s)
denotes the optimal offline algorithm with buffer s. Subsequently, they showed that on any
instance the costs of Opt(k/4) and Opt(k) can differ by a factor of at most O(log k). This implies
that Map is O(4 · log k) = O(log k)-competitive.
As shown by Aboud [Abo08], for the uniform metric space the relation between Opt(k/4) and
Opt(k) cannot be asymptotically improved, which excludes the option of beating the ratio O(log k)
by the described two-stage process. Note that this does not rule out the possibility of decreasing
the ratio by another approach. Indeed, subsequent works gave improved results, essentially
resolving
p the uniform metric case for deterministic algorithms: Adamaszek et al. [ACER11] gave
strategy and showed that the competitive ratio of every
an O( log k)-competitive deterministic
p
deterministic algorithm is Ω( log k/ log log k).

1.2 Two-stage approach for line metrics (our result)
Arguably, the most uncharted territory is the line metric, or more specifically, a line graph consisting of n equidistant sites. There, the lower bound on the competitive ratio is only 2.154 [GS09]. On
the other hand, the best known strategy is an O(log n)-competitive algorithm MovingPartition
by Gamzu and Segev [GS09]. Note that achieving an upper bound of O(k) is possible for any
metric space [EW05], and hence the competitive ratio for line metrics is O(min{k, log n}). In this
paper, we show that it is not possible to improve this bound by the two-stage approach described
above, by proving the following result.
Theorem 1. Fix a line consisting of n equidistant sites, any k, and any constant δ ∈ (0, 1). There
exists an input sequence on which the ratio between the costs of Opt(k) and Opt((1 − δ) · k) is at least
Ω(min{k, log n}).
Our result has additional consequences for the two known online algorithms for the reordering
buffer problem: MovingPartition [GS09] and Pay [ER17].
A straightforward modification of the analysis in [GS09] shows that MovingPartition is in fact
O((h/k) · log n)-competitive against an optimal offline algorithm that has a larger buffer h > k.
Our result implies that, assuming log n = O(k), for h = k · (1 + ε) and a fixed ε > 0, this ratio is
asymptotically optimal.
Similarly, algorithm Pay [ER17] achieves a competitive ratio of O((h/k) · (log D + log k)) on trees
with hop-diameter D, and hence it is O((h/k) · (log n + log k))-competitive when applied to a
line metric. Therefore, Pay is asymptotically optimal for line metrics when when n = O(k) and
h = k · (1 + ε) for a fixed ε > 0.

2 Main construction
The main technical contribution of this paper is to show Theorem 1 for the case when the line
consists of exactly n = 2k + 1 sites. For such a setting, the key lemma given below yields the cost
separation of Ω(k) = Ω(log n). In the next section, we show how request grouping extends this
result from the case of n = 2k + 1 sites to arbitrary values of k and n.
Lemma 2. Fix two integers 0 < `0 < ` and a constant ε such that `0 = (1 − ε) · `. Assume that the line
consists of 2` + 1 equidistant sites. There exists an input sequence on which the ratio between the costs of
Opt(`) and Opt(`0 ) is at least ` · ε2 · (1 + ε)−1 · log−1
2 (1 + 1/ε).

2

16

3

2

1

0

15
0

14

0

13
1

12

1

0

11
10

0

sites

9
2

8

2

1

0

7
6

0

5
4

1

0

3
2

0

1
3

0
0

time

Figure 1: A phase of the input sequence for ` = 4 (or, a line of 17 sites). Horizontal dotted lines correspond
to sites, whereas vertical dotted lines correspond to integer times. The dashed lines indicate the
beginning and the end of the phase. Disks and squares denote respectively the regular requests
(annotated with their ranks) and the anchors (sets of ` + 1 auxiliary requests each). A block of rank
3 and its two sub-blocks of rank 2 are marked at the bottom left; the block contains one regular
request of rank 2. The thick line represents the basic trajectory. The thinly-bordered squares have
sides of length equal to powers of 2 and are drawn purely for clarity of the input construction.

We number the sites from 0 to 2` . For simplicity of the description, we associate times with
request arrivals: all requests arrive only during a step between two consecutive integer times.
For a single step, we will explicitly specify the positions of the requests arriving in this step
but not their time ordering, which is irrelevant. (If needed, one may assume that they arrive
in the increasing site numbering order.) The input sequence consists of phases, one of which we
describe below. Then, any subsequent phase is “mirrored” with respect to the previous one, i.e.,
the description is identical except for reversing the site numbering.
The phase consists of 2` steps and it begins at time 0. Each request is either regular or auxiliary.
Each regular request has a rank i from 0 to ` − 1 and their positions are defined by the recursive
construction of blocks described below.
For any integers q ∈ {1, . . . , `} and s ∈ {0, . . . , 2`−q − 1}, a (q, s)-block is a square portion of spacetime, consisting of all times in (2q · s, 2q · (s + 1)] and all sites in (2q · s, 2q · (s + 1)], where q is called the
rank of the block. For instance, the (`, 0)-block is the whole phase. Moreover, (q, s)-block contains
two sub-blocks: the (q − 1, 2s)-block and the (q − 1, 2s + 1)-block, see Figure 1. In each (q, s)-block a
unique request of rank q − 1 arrives at site 2q · (s + 1) in the step following time 2q · s; note that this
request is not contained in any of its two sub-blocks. Graphically, it is near the top left corner of
the block, and it is depicted as a disk in Figure 1.
In turn, auxiliary requests are grouped in sets of ` + 1 called anchors (squares in Figure 1). For
all j from 0 to 2` − 1, the j-th anchor arrives at site j in the step following time j.
Throughout the paper, any relative directions in the text pertain to this figure, e.g., “up” and

3

“right” mean “with growing site numbers” and “forward in time”, respectively.

2.1 Upper bound on the cost of the optimal algorithm with a larger buffer
Let the basic trajectory (depicted as a thick line in Figure 1) be the movement of a server that, for
all j from 0 to 2` − 1, remains at site j throughout the step between the integer times j and j + 1,
and moves directly from j to j + 1 at the integer time j + 1. Note that in the subsequent phase the
last site becomes site 0, and thus the basic trajectory remains continuous over multiple phases as
well.
Lemma 3. The cost of Opt(`) in a single phase is at most 2` .
Proof. We prove that an algorithm with buffer size ` that follows the basic trajectory, denoted
BT(`), yields a feasible solution. As its cost is clearly 2` , the lemma follows. First, all anchors
are served immediately by BT(`), without storing them in the buffer, as they arrive at a current
position of the server. Second, we will show that for each of ` possible ranks, BT(`) has at most
one regular request of the given rank in its buffer, and hence its buffer capacity is not exceeded.
To this end, observe that the j-th request of rank i arrives at site 2i+1 · j in a step following time
2i+1 · (j − 1). It is served at time 2i+1 · j by BT(`), i.e., right before the next request of this rank arrives.
In fact, the cost of BT(`) is optimal as the anchors placed at all sites force any algorithm with
buffer ` to traverse the whole line at least once per phase.


2.2 Lower bound on the cost of the optimal algorithm with a smaller buffer
In this part, we construct a lower bound that holds for any algorithm that has buffer ` or smaller.
Later, we apply this bound to Opt(`0 ); recall that `0 = (1 − ε) · `. Observe that any such algorithm
has to process each anchor as soon as it arrives, since the anchor has ` + 1 requests. Therefore, its
trajectory within the step between times j and j + 1 has to pass through site j. Informally speaking,
its trajectory has to touch or intersect the basic trajectory in all steps of the phase.
Regular requests inside a (q, s)-block are called new for this block, whereas regular requests that
arrived at any site in (2q · s, 2q · (s + 1)] before time 2q · s are called old for this block. Note that all
the old requests for the (q, s)-block are at a single site, namely at 2q · (s + 1). Recall that (q, s)-block
contains only one request not contained in its sub-blocks (with rank q − 1 and position at site
2q · (s + 1)).
For p, r ≥ 0, q ≥ 1, let T(p, q, r) be the minimal cost of any algorithm for serving a block of rank q,
assuming that at the beginning of the block, its buffer has space for p (new) requests and r old
requests for this block are already stored in the buffer. If the algorithm trajectory leaves the block,
T(p, q, r) accounts only for these parts of its trajectory that are contained completely inside the
block. We show the following lower bound on T(p, q, r).
Lemma 4. T(p, q, r) ≥ 2q − 1. Furthermore, for q ≥ 2,

T(p, q, r) ≥ min 2q + 2 · T(p + r, q − 1, 0) , T(p − 1, q − 1, 0) + T(p − 1, q − 1, r + 1)
T(p, q, r) ≥

2q + 2 · T(p + r, q − 1, 0)

if p ≥ 1 ,
if p = 0 .

Proof. The first inequality holds, because a block of rank q contains anchors at all its sites, and the
distance between the two most distant of those is 2q − 1. For the remaining two inequalities (for
q ≥ 2), we consider two possible behaviors of the algorithm.

4

1. The algorithm moves the server to site 2q · (s + 1) before time 2q · s + 2q−1 . That is, it moves
the server to the upper boundary of the block (or beyond) within the first half-time of the
block. The length of the part of the trajectory contained in the current block but not in its
sub-blocks is then at least 2 · 2q−1 (to the upper boundary and back). We may assume that
such movement serves all r old requests and also the unique new request of rank q − 1. For
the purpose of the lower bound, we may assume that this happens instantly after the block
begins. Consequently, for both sub-blocks there are no buffered old requests and the buffer
part occupied by them was freed. Therefore, in this case
T(p, q, r) ≥ 2q + 2 · T(p + r, q − 1, 0) .
2. The strategy does not make such movement before time 2q · s + 2q−1 . Note that this is only
possible for p ≥ 1 as the unique request of rank q − 1 (the top left corner of the block) will
be stored in the buffer, decreasing empty buffer space to p − 1. This request becomes old for
the later sub-block, but for the earlier sub-block there are no old requests. Therefore, in this
case we get
T(p, q, r) ≥ T(p − 1, q − 1, 0) + T(p − 1, q − 1, r + 1) .
Combining these two cases yields the lemma.



Note that the cost of Opt(`) in a single phase is at least T(`, `, 0). In this case, it is always possible
to take the second case of the recurrence relation above, which corresponds to the basic trajectory
behavior. T(`, `, 0) then expands into a sum of 2`−1 terms of the form T(1, 1, r). In our reasoning
we only need T(1, 1, r) ≥ 1 but a more careful argument could double this amount, resulting in
an (otherwise trivial) lower bound of 2` for the cost of Opt(`).
Lemma 5. Fix any η ∈ (0, 1). Let a = (1 + η) · log2 (1 + 1/η), bi = 2(2i − 1) · η for all i ≥ 0, and
τ(p, q, r) =


2q
· q − (1 + η)p − br .
a

Then, T(p, q, r) ≥ τ(p, q, r) for any p ≥ 0, q ≥ 1 and r ≥ 0.
Proof. The lemma follows by induction on q. Its basis corresponds to the case q = 1, where
T(p, 1, r) ≥ 1 ≥ 2/a = τ(0, 1, 0) ≥ τ(p, 1, r) .
The second inequality follows as a > 2 for any η ∈ (0, 1), whereas the last one follows from the fact
that τ decreases in both p and r.
To show the inductive step, by Lemma 4, it suffices to prove the following two inequalities (for
q ≥ 2 and r ≥ 0):
2q + 2τ(p + r, q − 1, 0) ≥ τ(p, q, r)

for p ≥ 0 ,

(1)

τ(p − 1, q − 1, 0) + τ(p − 1, q − 1, r + 1) ≥ τ(p, q, r)

for p ≥ 1 .

(2)

For (1), we first determine a bound on f (r) = (1 + η) · r − br + 1. By taking its derivative in r (i.e.,
1 + η − η · 2r+1 / log2 e), we observe that f is maximized at r0 = log2 (1 + 1/η) + log2 log2 e − 1, and
therefore
f (r) ≤ f (r0 ) = (1 + η) · (log2 (1 + 1/η) + log2 log2 e − log2 e − 1) + 2η + 1 ≤ (1 + η) log2 (1 + 1/η) = a .

5

Consequently, applying b0 = 0 as well, we obtain
2q + 2τ(p + r, q − 1, 0) =

 2q

2q
a + q − 1 − (1 + η)(p + r) − b0 ≥
q − (1 + η)p − br = τ(p, q, r) .
a
a

For (2), from the definition of bi it holds that (b0 + br+1 )/2 = br+1 /2 = (2r+1 − 1) · η = br + η, which
implies
!
2q
b0 + br+1
τ(p − 1, q − 1, 0) + τ(p − 1, q − 1, r + 1) =
q − 1 − (1 + η)(p − 1) −
a
2
!
q
2
b0 + br+1
=
q − (1 + η)p + η −
a
2

2q
q − (1 + η)p − br = τ(p, q, r) .

=
a
We now show how to prove the key lemma using Lemma 3 and applying Lemma 5 to Opt(`0 ).
Proof of Lemma 2. The whole phase is the block of rank `, with no buffered old requests and hence,
by the definition of T, T(`0 , `, 0) = T((1 − ε) · `, `, 0) is a lower bound for the cost of Opt(`0 ) in a single
phase. Using Lemma 5 with η = ε, we obtain
T((1 − ε) · `, `, 0) ≥

2` · (` − (1 + ε) · (1 − ε) · `)
ε2
= 2` · ` ·
.
(1 + ε) log2 (1 + 1/ε)
(1 + ε) log2 (1 + 1/ε)

On the other hand, the cost of Opt(`) is at most 2` by Lemma 3, and hence the lemma follows. 

3 Cost separation for arbitrary buffer sizes
First, we show that Lemma 2 may be “scaled up” appropriately, and then we extend it to show
Theorem 1.
Lemma 6. Fix positive integers ` and β, and a constant ε ∈ (0, 1). Assume that the line consists of at least
2` + 1 equidistant sites. There exists an input sequence on which the ratio between the costs of two optimal
algorithms, one with a buffer of at least β · ` and one with a buffer of at most β · (1 − ε) · `, is at least Ω(`).
Proof. First, we fix the input sequence whose existence is asserted by Lemma 2. In this input,
we replace each request by a packet consisting of β requests at the same site. In any optimal
solution, without loss of generality, all requests belonging to such a packet are processed together.
Therefore, what matters is how many packets can be kept in the buffers of both algorithms, i.e.,
at least ` in case of the first algorithm and at most (1 − ε) · ` in case of the second one. Hence, for
the assumed buffer capacities the cost separation is at least ` · ε2 · (1 + ε)−1 · log−1
2 (1 + 1/ε), which
is Ω(`) for a fixed ε.
Second, the result of Lemma 2 is still valid when the total number of line sites is not equal but
greater than 2` + 1. The requests arrive then only at the first 2` + 1 sites and the remaining ones
cannot help nor hinder the performance of any algorithm.

Proof of Theorem 1. Let m = blog2 (n − 1)c, i.e., m is the largest integer such that 2m + 1 ≤ n. We
consider two cases, and in each of them we lower-bound the cost ratio between Opt(k) and
Opt((1 − δ) · k).
1. If k < m, let ` = k, β = 1 and ε = δ. Lemma 6 now implies that the cost ratio is Ω(`) = Ω(k).

6

2. If k ≥ m, we may assume k ≥ 4/δ, as otherwise Ω(min{k, log n}) = Ω(1) and the theorem
follows trivially. Let ` = dm · δ/4e, β = bk/`c and ε = δ/2, so that β · ` ≤ k. On the other
hand, ` < k · δ/4 + 1 ≤ k · δ/2, hence β · ` > (k/` − 1) · ` = k − ` > k · (1 − δ/2), which finally
yields (1 − ε) · β · ` > (1 − δ/2)2 · k > (1 − δ) · k. Therefore Opt(k) and Opt((1 − δ) · k) fulfill the
conditions of Lemma 6, which now implies that the cost ratio is Ω(`) = Ω(m).
In both cases we obtain that the cost ratio is Ω(min{k, m}) = Ω(min{k, log n}).



References
[Abo08]

Amjad Aboud. Correlation clustering with penalties and approximating the reordering
buffer management problem. Master’s thesis, Computer Science Department, The
Technion — Israel Institute of Technology, 2008.

[ACER11] Anna Adamaszek, Artur Czumaj, Matthias Englert, and Harald Räcke. Almost tight
bounds for reordering buffer management. In Proc. 43rd ACM Symp. on Theory of
Computing (STOC), pages 607–616, 2011.
[AIMR15] Noa Avigdor-Elgrabli, Sungjin Im, Benjamin Moseley, and Yuval Rabani. On the
randomized competitive ratio of reordering buffer management with non-uniform
costs. In Proc. 42nd Int. Colloq. on Automata, Languages and Programming (ICALP), pages
78–90, 2015.
[AR10]

Noa Avigdor-Elgrabli and Yuval Rabani. An improved competitive algorithm for
reordering buffer management. In Proc. 21st ACM-SIAM Symp. on Discrete Algorithms
(SODA), pages 13–21, 2010.

[AR13]

Noa Avigdor-Elgrabli and Yuval Rabani. An optimal randomized online algorithm for
reordering buffer management. In Proc. 54th IEEE Symp. on Foundations of Computer
Science (FOCS), pages 1–10, 2013.

[ER17]

Matthias Englert and Harald Räcke. Improved reordering buffer management for trees
and general metrics. In Proc. 28th ACM-SIAM Symp. on Discrete Algorithms (SODA),
pages 1224–1234, 2017.

[ERW10]

Matthias Englert, Harald Räcke, and Matthias Westermann. Reordering buffers for
general metric spaces. Theory of Computing Systems, 6(1):27–46, 2010.

[EW05]

Matthias Englert and Matthias Westermann. Reordering buffer management for nonuniform cost models. In Proc. 32nd Int. Colloq. on Automata, Languages and Programming
(ICALP), pages 627–638, 2005.

[GS09]

Iftah Gamzu and Danny Segev. Improved online algorithms for the sorting buffer
problem on line metrics. ACM Transactions on Algorithms, 6(1), 2009.

[KP10]

Rohit Khandekar and Vinayaka Pandit. Online and offline algorithms for the sorting
buffers problem on the line metric. Journal of Discrete Algorithms, 8(1):24–35, 2010.

[RSW02]

Harald Räcke, Christian Sohler, and Matthias Westermann. Online scheduling for
sorting buffers. In Proc. 10th European Symp. on Algorithms (ESA), pages 820–832, 2002.

7

