{"id":"arxiv/2611.01177","url":"https://arxiv.org/abs/2611.01177","tags":["cs.DS","math.CO"],"score":0,"title":"Fluid Limits and Upper Bounds for Randomized Greedy Matching","domain":"cs.DS","source":"arxiv","authors":["Sayan Mukherjee"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-31","reactions":{}}