A short proof of the 1-1/e performance of RANKING on the complete upper triangular instance
Giovanni Montanari, Nadav Merlis, Simon Mauras, Vianney Perchet
原文摘要
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.
cs.DS