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).