An Optimal Randomized Online Algorithm for Reordering Buffer Management

Noa Avigdor-elgrabli, Yuval Rabani

We give an $O(\log \log k)$-competitive randomized online algorithm for reordering buffer management, where $k$ is the buffer size. Our bound matches the lower bound of Adamaszek et…