Metraipolis › archive › dc_f95e43388ecd
Nearly-Linear Query Algorithm for Submodular Maximization subject to a Matroid Constraint — arXiv:2611.05021
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05021
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T19:07:41.510Z
- SHA-256 of the archived text
4fead1cfc356e91540e2a6bd06dc681a829001a95a9ff10994929eb48266b6a0- Stable URL of this page
https://metraipolis.com/documento/dc_f95e43388ecd
How to cite
Nearly-Linear Query Algorithm for Submodular Maximization subject to a Matroid Constraint — arXiv:2611.05021 — arXiv (en), https://arxiv.org/abs/2611.05021 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f95e43388ecd (Metraipolis archive dc_f95e43388ecd, sha256 4fead1cfc356e91540e2a6bd06dc681a829001a95a9ff10994929eb48266b6a0)
BibTeX
@misc{dcf95e43388ecd,
title = {Nearly-Linear Query Algorithm for Submodular Maximization subject to a Matroid Constraint — arXiv:2611.05021},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05021},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f95e43388ecd; sha256 4fead1cfc356e91540e2a6bd06dc681a829001a95a9ff10994929eb48266b6a0},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05021. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We consider monotone submodular maximization subject to a matroid constraint. The seminal continuous greedy algorithm of Calinescu, Chekuri, Pál, and Vondrák~[SICOMP'11] achieves the tight approximation of $(1-1/e)$. Since then, a line of works by Badanidiyuru and Vondrák~[SODA'14], Buchbinder, Feldman, and Schwartz~[SODA'15 \& MOR'17], Kobayashi and Terao~[ICALP'24], Buchbinder and Feldman~[FOCS'24 \& SICOMP'25], and Buchbinder and Feldman~[STOC'25] has developed efficient $(1-1/e-\varepsilon)$-approximation algorithms for this problem. We present a combinatorial randomized $(1-1/e-\varepsilon)$-approximation algorithm that requires $\tilde{O}_{\varepsilon}(n)$ independence-oracle and value-oracle queries, where $n$ is the number of elements in the matroid. This is the first $(1-1/e-\varepsilon)$-approximation algorithm with both independence-oracle and value-oracle query complexities nearly-linear in $n$ and polynomial in $1/\varepsilon$. To achieve this, we develop a new local search algorithm, which we call \emph{protected local search}, based on the potential function of Buchbinder and Feldman~[FOCS'24 \& SICOMP'25].
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.05021 — 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-04T18:40:52.476Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).