An Economic-Based Analysis of RANKING for Online Bipartite Matching
share
We give a simple proof showing that the RANKING algorithm introduced by Karp, Vazirani and Vazirani DBLP:conf/stoc/KarpVV90 is 1-1/e competitive for the online bipartite matching problem. Our proof resembles the proof given by Devanur, Jain and Kleinberg [2013], but does not make an explicit use of linear programming duality; instead, it is based on an economic interpretation of the matching problem. In our interpretation, one set of vertices represent items that are assigned prices, and the other set of vertices represent unit-demand buyers that arrive sequentially and choose their most-demanded items.
READ FULL TEXT