Nearly-Linear Query Algorithm for Submodular Maximization subject to a Matroid Constraint

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-ε)-approximation algorithms for this problem. We present a combinatorial randomized (1-1/e-ε)-approximation algorithm that requires Õε(n) independence-oracle and value-oracle queries, where n is the number of elements in the matroid. This is the first (1-1/e-ε)-approximation algorithm with both independence-oracle and value-oracle query complexities nearly-linear in n and polynomial in 1/ε. To achieve this, we develop a new local search algorithm, which we call protected local search, based on the potential function of Buchbinder and Feldman~[FOCS'24 & SICOMP'25].