A short proof of the 1-1/e performance of RANKING on the complete upper triangular instance

Giovanni Montanari, Nadav Merlis, Simon Mauras, Vianney PerchetarXiv 2026 · arXiv

Abstract

The randomized online bipartite matching algorithm RANKING of Karp, Vazirani and Vazirani (1990) matches, asymptotically, a fraction $1-1/e$ of the vertices of the complete upper triangular (CUT) instance. We give a short proof of this fact that looks at the final matching from the offline side. A single observation drives the argument: the first $k$ arrivals can distinguish the offline vertices $v_k,\ldots,v_n$ only through their ranks. As a consequence, whether $v_k$ is matched is decided by a uniform draw among the remaining ranks, and the number of matched vertices among $v_1,\ldots,v_k$ is a Markov chain with explicit transition probabilities. A linear differential equation, solved by hand, gives the limiting profile of this chain, and the constant $1/e$ appears where the matching probability reaches one.
BibTeX
@misc{montanari2026short,
  author = {Giovanni Montanari and Nadav Merlis and Simon Mauras and Vianney Perchet},
  title = {{A short proof of the 1-1/e performance of RANKING on the complete upper triangular instance}},
  year = {2026},
  eprint = {2611.22923},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22923},
}

Loading related content...

Figure