Metraipolis › archive › dc_b2bbd6ab65d1
The Power of Local Marginals: An $O(\varepsilon^{-1})$-Aspect-Ratio Reduction for Dynamic Weighted Matching — arXiv:2608.27805
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.27805
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T11:52:23.594Z
- SHA-256 of the archived text
a020f113127838a91fb3927822da132c39a2fac25d7de5c5d1f0c89e1879abf5- Stable URL of this page
https://metraipolis.com/documento/dc_b2bbd6ab65d1
How to cite
The Power of Local Marginals: An $O(\varepsilon^{-1})$-Aspect-Ratio Reduction for Dynamic Weighted Matching — arXiv:2608.27805 — arXiv (en), https://arxiv.org/abs/2608.27805 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b2bbd6ab65d1 (Metraipolis archive dc_b2bbd6ab65d1, sha256 a020f113127838a91fb3927822da132c39a2fac25d7de5c5d1f0c89e1879abf5)
BibTeX
@misc{dcb2bbd6ab65d1,
title = {The Power of Local Marginals: An $O(varepsilon^-1)$-Aspect-Ratio Reduction for Dynamic Weighted Matching — arXiv:2608.27805},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.27805},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b2bbd6ab65d1; sha256 a020f113127838a91fb3927822da132c39a2fac25d7de5c5d1f0c89e1879abf5},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.27805. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study dynamic maximum weight matching under edge insertions and deletions in two settings: maintaining a $(1\pm\varepsilon)$-approximation to the optimum weight, and maintaining an explicit $(1-\varepsilon)$-approximate matching. Our main result is a reduction that transforms instances of polynomial aspect ratio into instances of aspect ratio $O(\varepsilon^{-1})$. The reduction applies to general graphs in both settings and is compatible with partially dynamic updates. The reduction is based on a structural property of local marginals. After grouping edges into weight classes, the global marginal contribution of one class relative to all lower classes is approximated by its marginal contribution within a local weight window of aspect ratio $O(\varepsilon^{-1})$. Summing these local marginals yields a value composition lemma that approximates the optimum weight in the entire graph with approximate optimum weights of the local windows. This improves the value reduction of Gupta and Peng (FOCS 2013), whose local aspect ratio is $\varepsilon^{-\Theta(\varepsilon^{-1})}$. The same structural property yields an improved matching composition lemma for explicit matchings, reducing the local aspect ratio of Bernstein--Chen--Dudeja--Langley--Sidford--Tu (SODA 2025) from $O(\varepsilon^{-2})$ to $O(\varepsilon^{-1})$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-31 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.27805 — 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-10-17T11:23:11.253Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-31?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).