Fluid Limits and Upper Bounds for Randomized Greedy Matching
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.01177
curl -X POST /api/v1/records/arxiv/2611.01177/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.01177/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'