Fluid Limits and Upper Bounds for Randomized Greedy Matching
Published in arXiv Preprint, 2026
We disprove a 35-year old conjecture on the upper bound of the approximation ratio of a classical greedy matching algorithm.
Recommended citation: Sayan Mukherjee. "Fluid Limits and Upper Bounds for Randomized Greedy Matching." arXiv Preprint arXiv:2611.01177 https://arxiv.org/abs/2611.01177
