#
A constant factor approximation algorithm for reordering buffer management

##
Christopher Wood

In the reordering buffer management problem (RBM) a sequence of n
colored items enters a buffer with limited capacity $k$. When the buffer
is full, one item is removed to the output sequence, making room for the
next input item. This step is repeated until the input sequence is
exhausted and the buffer is empty. The objective is to find a sequence of
removals that minimizes the total number of color changes in the output
sequence. The problem formalizes numerous applications in computer and
production systems, and is known to be NP-hard.

We give the first constant factor approximation guarantee for RBM. Our
algorithm is based on an intricate “rounding” of the
solution to an LP
relaxation for RBM, so it also establishes a constant upper bound on the
integrality gap of this relaxation. Our results improve upon the best
previous bound of $O(\sqrt{\log k})$ of Adamaszek et al. (STOC 2011) that
used different methods and gave an online algorithm. Our constant factor
approximation beats the super-constant lower bounds on the competitive
ratio given by Adamaszek et al. This is the first demonstration of an
offline algorithm for RBM that is provably better than any online
algorithm.

(From a paper by Noa
Avigdor-Elgrabli and Yuval Rabani at SODA 2013.)