Metraipolis › archive › dc_7baf22df5e7d
Optimal Sample Complexity for Max-Cut — arXiv:2611.03205
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.03205
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T18:59:02.264Z
- SHA-256 of the archived text
927fa198333215d1a2190779dac8e7ebb6d8a9e7c26e9af5194aea996dc84512- Stable URL of this page
https://metraipolis.com/documento/dc_7baf22df5e7d
How to cite
Optimal Sample Complexity for Max-Cut — arXiv:2611.03205 — arXiv (en), https://arxiv.org/abs/2611.03205 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7baf22df5e7d (Metraipolis archive dc_7baf22df5e7d, sha256 927fa198333215d1a2190779dac8e7ebb6d8a9e7c26e9af5194aea996dc84512)
BibTeX
@misc{dc7baf22df5e7d,
title = {Optimal Sample Complexity for Max-Cut — arXiv:2611.03205},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.03205},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7baf22df5e7d; sha256 927fa198333215d1a2190779dac8e7ebb6d8a9e7c26e9af5194aea996dc84512},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03205. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We determine the optimal sample size for constructing value coresets for Max-Cut via uniform vertex sampling. That is, sampling $O(\varepsilon^{-2})$ vertices uniformly at random in $n$-vertex graphs with edge weights in $[0,1]$ yields a reweighted subgraph whose Max-Cut value is an additive $\varepsilon n^2$-approximation to that of the original graph, with constant success probability. This improves the previously known $O(\varepsilon^{-4})$ upper bound and matches the known lower bound. The same guarantee holds also for importance sampling, where vertices are sampled proportionally to their weighted degrees, and we further prove a matching lower bound for this sampling method. Our analysis extends directly to metric Max-Cut, showing that importance sampling of $O(\varepsilon^{-2})$ vertices yields $(1\pm\varepsilon)$-approximation to the Max-Cut value, and to Max-Cut in graphs with edge weights in $[0,1]$ and average weighted degree $\bar d$, achieving the same $(1\pm\varepsilon)$-approximation by either uniform or importance sampling of $O(\varepsilon^{-2}n/\bar d)$ vertices. We additionally show how to use this coreset to recover a cut of expected value at least $OPT-\varepsilon n^2$, by making $O(n\varepsilon^{-2})$ additional edge-weight queries. Finally, our result extends to Max-$r$-Cut, giving an additive $\varepsilon n^2$-approximation using a sample of $O(\varepsilon^{-2}\log(2r))$ vertices.
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.03205 — 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-03T18:18:07.749Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).