# Random-Order Models

arXiv: https://arxiv.org/abs/2002.12159 · HTML: https://mlsanity.com/paper/2002.12159/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2020.

## Built on by (most cited first, 6 of 6)

- [Online Combinatorial Allocations and Auctions with Few Samples](https://mlsanity.com/paper/2409.11091/) (2024)
- [Single-Sample and Robust Online Resource Allocation](https://mlsanity.com/paper/2505.02963/) (2025)
- [Online Learning in the Random Order Model](https://mlsanity.com/paper/2510.02820/) (2025)
- [The Secretary Problem with Predictions and a Chosen Order](https://mlsanity.com/paper/2601.07482/) (2026)
- [Fairness in the Multi-Secretary Problem](https://mlsanity.com/paper/2511.23097/) (2025)
- [From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model](https://mlsanity.com/paper/2602.09457/) (2026)

## Abstract (arXiv)

This chapter introduces the random-order model in online algorithms. In this model, the input is chosen by an adversary, then randomly permuted before being presented to the algorithm. This reshuffling often weakens the power of the adversary and allows for improved algorithmic guarantees. We show such improvements for two broad classes of problems: packing problems where we must pick a constrained set of items to maximize total value, and covering problems where we must satisfy given requirements at minimum total cost. We also discuss how random-order model relates to other stochastic models used for non-worst-case competitive analysis.