A 0.51-Approximation of Maximum Matching in Sublinear n^1.5 Time - Mahabadi, Sepideh; Roghani, Mohammad; Tarnawski, Jakub (ICALP 2025, 2025)
We study the problem of estimating the size of a maximum matching in sublinear time. The problem has been studied extensively in the literature and various algorithms and lower bounds are known for it. Our result is a 0.5109-approximation algorithm with a running time of [O](n[n]). All previous algorithms either provide only a marginal improvement (e.g., 2^[-280]) over the 0.5-approximation that arises from estimating a [maximal] matching, or have a running time that is nearly n^2. Our approach is also arguably much simpler than other algorithms beating 0.5-approximation.