Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint
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.
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}
}
EUVIMED