## 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 language | English (US) |
---|---|

Pages (from-to) | 133-150 |

Number of pages | 18 |

Journal | Stochastic Systems |

Volume | 12 |

Issue number | 2 |

DOIs | |

State | Published - Jun 2022 |

Externally published | Yes |

### Bibliographical note

Publisher Copyright:© 2021 The Author(s).

## Keywords

- greedy algorithms
- matching
- random graphs