Greedy Matching in Bipartite Random Graphs
| Autor: | Nick Arnosti |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
Statistics and Probability
Random graph Matching (graph theory) Computer science Computer Science::Information Retrieval Astrophysics::Instrumentation and Methods for Astrophysics Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Management Science and Operations Research Combinatorics TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Modeling and Simulation ComputingMethodologies_DOCUMENTANDTEXTPROCESSING Bipartite graph Computer Science::General Literature Enhanced Data Rates for GSM Evolution Statistics Probability and Uncertainty Focus (optics) Greedy algorithm ComputingMilieux_MISCELLANEOUS |
| Zdroj: | Stochastic Systems. 12:133-150 |
| ISSN: | 1946-5238 |
| Popis: | This paper studies the performance of greedy matching algorithms on bipartite graphs [Formula: see text]. We focus primarily on three classical algorithms: [Formula: see text], which sequentially selects random edges from [Formula: see text]; [Formula: see text], which sequentially matches random vertices in [Formula: see text] to random neighbors; and [Formula: see text], which generates a random priority order over vertices in [Formula: see text] and then sequentially matches random vertices in [Formula: see text] 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 [Formula: see text] and lowest for [Formula: see text]. Our work instead studies the average performance of these algorithms when the edge set [Formula: see text] is random. Our first result compares [Formula: see text] and [Formula: see text] and shows that on average, [Formula: see text] produces more matches. This result holds for finite graphs (in contrast to previous asymptotic results) and also applies to “many to one” matching in which each vertex in [Formula: see text] can match with multiple vertices in [Formula: see text]. Our second result compares [Formula: see text] and [Formula: see text] and shows that the better worst-case guarantee of [Formula: see text] does not translate into better average performance. In “one to one” settings where each vertex in [Formula: see text] can match with only one vertex in [Formula: see text], the algorithms result in the same number of matches. When each vertex in [Formula: see text] can match with two vertices in [Formula: see text] produces more matches than [Formula: see text]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|