Greedy Matching in Bipartite Random Graphs

This paper studies the performance of greedy matching algorithms on bipartite graphs G = (J, D, E). We focus primarily on three classical algorithms: RANDOM-EDGE, which sequentially selects random edges from E; RANDOM-VERTEX, which sequentially matches random vertices in J to random neighbors; and RANKING, which generates a random priority order over vertices in D and then sequentially matches random vertices in J to their highest-priority remaining neighbor. Prior work has focused on identifying the worst-case approximation ratio for each algorithm. This guarantee is highest for RANKING and lowest for RANDOM-EDGE. Our work instead studies the average performance of these algorithms when the edge set E is random. Our first result compares RANDOM-VERTEX and RANDOM-EDGE and shows that on average, RANDOM-VERTEX produces more matches. This result holds for finite graphs (in con-trast to previous asymptotic results) and also applies to “many to one” matching in which each vertex in D can match with multiple vertices in J. Our second result compares RANDOM-VERTEX and RANKING and shows that the better worst-case guarantee of RANKING does not translate into better average performance. In “one to one” settings where each vertex in D can match with only one vertex in J, the algorithms result in the same number of matches. When each vertex in D can match with two vertices in J, RANDOM-VERTEX produces more matches than RANKING.