A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913870838235136 |
|---|---|
| author | Mahabadi, Sepideh Roghani, Mohammad Tarnawski, Jakub |
| author_facet | Mahabadi, Sepideh Roghani, Mohammad Tarnawski, Jakub |
| contents | 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 $\tilde{O}(n\sqrt{n})$.
All previous algorithms either provide only a marginal improvement (e.g., $2^{-280}$) over the $0.5$-approximation that arises from estimating a \emph{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_01669 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time Mahabadi, Sepideh Roghani, Mohammad Tarnawski, Jakub Data Structures and Algorithms 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 $\tilde{O}(n\sqrt{n})$. All previous algorithms either provide only a marginal improvement (e.g., $2^{-280}$) over the $0.5$-approximation that arises from estimating a \emph{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. |
| title | A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.01669 |