An Economic-Based Analysis of RANKING for Online Bipartite Matching

Alon Eden, Michal Feldman, Amos Fiat +1

In their seminal paper, Karp, Vazirani and Vazirani (STOC'90) introduce the online bipartite matching problem, and the RANKING algorithm, which admits a tight $1-\frac{1}{e}$ compe…