Changes

Motivated by practical applications in real-world, we assume we have prior stochastic information about the input. In particular we know the colors of items are drawn i.i.d.  from a possibly  unknown distribution or more generally the items are coming in the random order setting in which an adversary determines the color of each item in advance, but then the items arrive in a random order in the input stream. To the best of our knowledge, this is the first work which considers the reordering buffer problem in stochastic settings.

Motivated by practical applications in real-world, we assume we have prior stochastic information about the input. In particular we know the colors of items are drawn i.i.d.  from a possibly  unknown distribution or more generally the items are coming in the random order setting in which an adversary determines the color of each item in advance, but then the items arrive in a random order in the input stream. To the best of our knowledge, this is the first work which considers the reordering buffer problem in stochastic settings.

Our main result is demonstrating constant competitive online algorithms for both the standard model and the block operation model in the unknown distribution setting and more generally in the random order setting. This provides a major improvement of the competitiveness of algorithms in stochastic settings; the best competitive ratio in the adversarial setting is \Theta(log (log (k)) for both the standard and the block-operation models by Avigdor-elgrabli and Rabani and Adamaszek et al.

Our main result is demonstrating constant competitive online algorithms for both the standard model and the block operation model in the unknown distribution setting and more generally in the random order setting. This provides a major improvement of the competitiveness of algorithms in stochastic settings; the best competitive ratio in the adversarial setting is \Theta(log (log (k)) for both the standard and the block-operation models by Avigdor-elgrabli and Rabani and Adamaszek et al.

Along the way, we also show that in the random order setting designing competitive algorithms with the same competitive ratios (up to constant factors) in both the block operation model and the standard model are equivalent.

Along the way, we also show that in the random order setting designing competitive algorithms with the same competitive ratios (up to constant factors) in both the block operation model and the standard model are equivalent.