A short proof of the 1-1/e performance of RANKING on the complete upper triangular instance
Lists
Only you see this
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...