A Constant Factor Approximation Algorithm for Reordering Buffer Management

Noa Avigdor-Elgrabli, Yuval Rabani

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 out…