Greedy Matching in Bipartite Random Graphs

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)133-150
Number of pages18
JournalStochastic Systems
Volume12
Issue number2
DOIs
StatePublished - Jun 2022

Bibliographical note

Publisher Copyright:
© 2021 The Author(s).

Keywords

  • greedy algorithms
  • matching
  • random graphs

Fingerprint

Dive into the research topics of 'Greedy Matching in Bipartite Random Graphs'. Together they form a unique fingerprint.

Cite this