EUVIMEDEUVIMED entdecken
Crossref

Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint

Niv Buchbinder, Moran Feldman

SIAM Journal on Computing · 31.10.2026 · 55 (5) · FOCS24-85-FOCS24-114

DOI: 10.1137/24m1698122 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 02.12.2025. Verfasst von Niv Buchbinder und 1 weiteren Autor:innen. Die Arbeit nennt 56 Literaturangaben. Gefördert von: Israel Science Foundation, United States - Israel Binational Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the problem of maximizing a monotone submodular function subject to a matroid constraint, and present for it a deterministic nonoblivious local search algorithm that has an approximation guarantee of [Formula: see text] (for any [Formula: see text]) and query complexity of [Formula: see text], where [Formula: see text] is the size of the ground set and [Formula: see text] is the rank of the matroid. Our algorithm vastly improves over the previous state-of-the-art 0.5008-approximation deterministic algorithm, and in fact shows that there is no separation between the approximation guarantees that can be obtained by deterministic and randomized algorithms for the problem considered. The query complexity of our algorithm can be improved to [Formula: see text] using randomization, which is nearly linear for [Formula: see text], and is always at least as good as the previous state-of-the-art algorithms.

Förderung

  • Israel Science Foundation
  • United States - Israel Binational Science Foundation

Zitieren

APA

Buchbinder, N., & Feldman, M. (2026). Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint. SIAM Journal on Computing, 55(5), FOCS24-85-FOCS24-114. https://doi.org/10.1137/24m1698122

Vancouver

Buchbinder N, Feldman M. Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint. SIAM Journal on Computing. 2026;55(5):FOCS24-85-FOCS24-114. doi:10.1137/24m1698122

BibTeX
@article{Buchbinder2026,
  author = {Buchbinder, Niv and Feldman, Moran},
  title = {Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {5},
  pages = {FOCS24--85--FOCS24--114},
  doi = {10.1137/24m1698122}
}
Kostenlos starten →