  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 al. (STOC 2011). Our algorithm has two stages
which are executed online in parallel. The first stage computes
deterministically a feasible fractional solution to an LP relaxation for
reordering buffer management. The second stage "rounds" using randomness the
fractional solution. The first stage is based on the online primal-dual schema,
combined with a dual fitting argument. As multiplicative weights steps and dual
fitting steps are interleaved and in some sense conflicting, combining them is
challenging. We also note that we apply the primal-dual schema to a relaxation
with mixed packing and covering constraints. We pay the $O(\log\log k)$
competitive factor for the gap between the computed LP solution and the optimal
LP solution. The second stage gives an online algorithm that converts the LP
solution to an integral solution, while increasing the cost by an O(1) factor.
This stage generalizes recent results that gave a similar approximation factor
for rounding the LP solution, albeit using an offline rounding algorithm.
