Fluid Limits and Upper Bounds for Randomized Greedy Matching
Abstract
The Modified Randomized Greedy (MRG) algorithm [Tinhofer (1984), Aronson-Dyer-Frieze-Suen (1995)] is a classical greedy algorithm for finding approximate maximum matchings. MRG repeatedly picks a uniformly random unmatched vertex and matches it to a uniformly random unmatched neighbor, if one exists. Since 1991, the best upper bound on its approximation ratio has been 2/3, given by the Bomb graphs of [Dyer and Frieze (1991)]. We improve this bound to $0.6569$ on general graphs and $0.6607$ on bipartite graphs. Our constructions consist of copies of small gadgets, with specified vertex classes joined completely. We track each algorithm by counting gadget copies with each possible configuration of remaining vertices. Wormald's differential equation method [Wormald (1995)] shows that these counts, scaled by the size parameter of the construction, converge to a deterministic trajectory known as the \textit{fluid limit}, which is described by ordinary differential equations. This fluid limit approximation holds while the relevant vertex classes have positive density, and so we devise a separate counting argument determines the contribution from the end of the run. Furthermore, we apply our framework to Random Decision Order (RDO), in which vertices are processed in uniformly random order and choose unmatched neighbors according to fixed adversarial preferences. On bipartite graphs, we determine the exact limiting ratio on the Double-Bomb family of [Tang-Wu-Zhang (2020)]. Its minimum is 31/48, confirming their numerical estimate of about $0.646$.On general graphs, we improve their upper bound of 5/8, given by the paw graph, to $0.5946$ on a new family. Finally, we give one possible explanation for why 2/3 seemed to be optimal for MRG in the concluding remarks.
Related
- Matching Randomized First-Order Bounds for Higher-Order Smooth Nonconvex Optimization
- Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization
- Matching Randomized Bounds for Finite-Sum Nonconvex-Concave Optimization
- The terminal leave in random greedy hypergraph matching
- Degree Stability of Parallel Greedy Matching in Random Graphs
BibTeX
@misc{mukherjee2026fluid,
title = {{Fluid Limits and Upper Bounds for Randomized Greedy Matching}},
author = {Sayan Mukherjee},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01177},
eprint = {2611.01177},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01177},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Fluid Limits and Upper Bounds for Randomized Greedy Matching
AU - Sayan Mukherjee
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01177
UR - https://arxiv.org/abs/2611.01177
AB - The Modified Randomized Greedy (MRG) algorithm [Tinhofer (1984), Aronson-Dyer-Frieze-Suen (1995)] is a classical greedy algorithm for finding approximate maximum matchings. MRG repeatedly picks a uniformly random unmatched vertex and matches it to a uniformly random unmatched neighbor, if one exists. Since 1991, the best upper bound on its approximation ratio has been 2/3, given by the Bomb graphs of [Dyer and Frieze (1991)]. We improve this bound to $0.6569$ on general graphs and $0.6607$ on bipartite graphs. Our constructions consist of copies of small gadgets, with specified vertex classes joined completely. We track each algorithm by counting gadget copies with each possible configuration of remaining vertices. Wormald's differential equation method [Wormald (1995)] shows that these counts, scaled by the size parameter of the construction, converge to a deterministic trajectory known as the \textit{fluid limit}, which is described by ordinary differential equations. This fluid limit approximation holds while the relevant vertex classes have positive density, and so we devise a separate counting argument determines the contribution from the end of the run. Furthermore, we apply our framework to Random Decision Order (RDO), in which vertices are processed in uniformly random order and choose unmatched neighbors according to fixed adversarial preferences. On bipartite graphs, we determine the exact limiting ratio on the Double-Bomb family of [Tang-Wu-Zhang (2020)]. Its minimum is 31/48, confirming their numerical estimate of about $0.646$.On general graphs, we improve their upper bound of 5/8, given by the paw graph, to $0.5946$ on a new family. Finally, we give one possible explanation for why 2/3 seemed to be optimal for MRG in the concluding remarks.
ER -