Metraipolis › archive › dc_87e79cd76267
Optimal LCA and Sublinear Estimation for Bipartite Matching in $Δ^{O(1/\varepsilon)}$ Queries — arXiv:2611.06024
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.06024
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:31:37.042Z
- SHA-256 of the archived text
1f837b37481adb4651c83d17c93f2a6444d592cb4e9628c22ee00e520a9c955f- Stable URL of this page
https://metraipolis.com/documento/dc_87e79cd76267
How to cite
Optimal LCA and Sublinear Estimation for Bipartite Matching in $Δ^{O(1/\varepsilon)}$ Queries — arXiv:2611.06024 — arXiv (en), https://arxiv.org/abs/2611.06024 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_87e79cd76267 (Metraipolis archive dc_87e79cd76267, sha256 1f837b37481adb4651c83d17c93f2a6444d592cb4e9628c22ee00e520a9c955f)
BibTeX
@misc{dc87e79cd76267,
title = {Optimal LCA and Sublinear Estimation for Bipartite Matching in $Δ^O(1/varepsilon)$ Queries — arXiv:2611.06024},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.06024},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_87e79cd76267; sha256 1f837b37481adb4651c83d17c93f2a6444d592cb4e9628c22ee00e520a9c955f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06024. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A local computation algorithm (LCA) for matching answers ``who is the mate of $v$?'' by inspecting only a small part of the graph, with all answers consistent with one matching. For $n$-vertex graphs of maximum degree $\Delta\ge2$, Levi et al. [Algorithmica'17] give a $(1-\varepsilon)$-approximate matching LCA using $(\Delta/\varepsilon)^{O(1/\varepsilon^2)} \operatorname{polylog}(n)$ queries per invocation, while Yoshida et al. [SIAM J. Comput.'12] estimate the maximum matching size within additive error $\varepsilon n$ using $\Delta^{O(1/\varepsilon^2)}$ queries. Behnezhad, Roghani, and Rubinstein [FOCS'23] proved a $\Delta^{\Omega(1/\varepsilon)}$ lower bound for both tasks, even on bipartite graphs and even when the LCA's matching guarantee is relaxed to additive $\varepsilon n$ error. This leaves a gap between linear and quadratic dependence on $1/\varepsilon$ in the exponent. We close this gap on bipartite graphs. We give an LCA that answers each mate query with $\Delta^{O(1/\varepsilon)}$ queries for a $(1-\varepsilon)$-approximate matching, and an estimator for the maximum matching size within $\varepsilon n$ using $\Delta^{O(1/\varepsilon)}$ queries. On general graphs, the same algorithm gives a half-integral fractional matching and estimates the maximum fractional matching size. Our approach runs $O(\varepsilon^{-1}\log\Delta)$ rounds of a deterministic local optimization method in which vertices propose to neighbors and update prices according to incoming loads. We design its updates to admit exact recursive sampling with constant expected branching, obtaining the improved randomized bound without exploring full dependency neighborhoods. To our knowledge, this is the first LCA construction based on exact recursive sampling of the iterates of a deterministic continuous optimization method. We expect this approach to have applications beyond matching.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.06024 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:21:04.026Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).