# Theory Seminar: A constant factor approximation algorithm for reordering buffer management

- Speaker:
- Noa Avigdor-Elgrabli (CS, Technion)
- Date:
- Wednesday, 23.1.2013, 12:30
- Place:
- Taub 201

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 a polynomial time offline algorithm for
RBM that is provably better than any online algorithm.