2026-08-19T02:48:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23493 2025-10-02T12:56:47Z ddc:004 open_access

A 0.51-Approximation of Maximum Matching in Sublinear n^{1.5} Time Mahabadi, Sepideh Roghani, Mohammad Tarnawski, Jakub Sublinear Algorithms Maximum Matching Maximal Matching Approximation Algorithm 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 Õ(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². Our approach is also arguably much simpler than other algorithms beating 0.5-approximation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sepideh Mahabadi and Mohammad Roghani and Jakub Tarnawski 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.116 urn:nbn:de:0030-drops-234932 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.116 eng https://creativecommons.org/licenses/by/4.0/legalcode