2025/06/02 by Mahabadi, Sepideh, Roghani, Mohammad, Tarnawski, Jakub · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2506.01669
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 n2. Our approach is also arguably much simpler than other algorithms beating 0.5-approximation.