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].
In the graphic matroid parity problem, we are given an undirected multigraph $G=(V,E)$ with $n$ vertices, together with a partition of $E$ into $m$ pairs of distinct edges, and the goal is to find a maximum-cardinality collection of pairs whose union is a forest. This problem generalizes both graph matching and graphic matroid intersection. Graph matching admits the celebrated $\tilde{O}(\sqrt{n}m)$-time algorithm of Micali--Vazirani~[FOCS'80], and graphic matroid intersection admits $o(nm)$-time algorithms due to Gabow--Stallmann~[ICALP'85] and Gabow--Xu~[FOCS'89]. In contrast, for graphic matroid parity, Gabow--Stallmann~[FOCS'84 \& Combinatorica'86] gave an $O(n^2 m)$-time algorithm, and its $\tilde{O}(nm)$-time implementation by Gabow--Stallmann~[ICALP'85] had long remained the best known bound, except in very dense regimes where $m=ω(n^3)$, in which case the algebraic $\tilde{O}(n^4)$-time algorithm of Cheung--Lau--Leung~[SODA'11 \& TALG'14] is faster. We present a randomized $\tilde{O}(n^{3/2} \sqrt{m} + \sqrt{n} m)$-time algorithm for graphic matroid parity. This is the first algorithm to break the $O(nm)$-time complexity barrier for this problem outside the very dense regime. Moreover, it improves over the previous bounds except in very sparse regimes where $m=\tilde{O}(n)$ and in very dense regimes where $m = \tildeΩ(n^{3.5})$. In particular, when $m=Θ(n^2)$, our algorithm runs in $\tilde{O}(n^{2.5})$ time, which nearly matches the $\tilde{O}(n^{2.5})$-time bounds of Micali--Vazirani for graph matching and of Gabow--Xu for graphic matroid intersection in this regime.
We consider the weighted matroid intersection problem in the independence-oracle model. A sequence of works by Huang--Kakimura--Kamiyama~[SODA'16 \& Math. Program'19], Chekuri--Quanrud~[SODA'16], Quanrud~[ICALP'24], and Dudeja--Grilnberger~[IPCO'26] has developed efficient $(1-\varepsilon)$-approximation algorithms for this problem. We present a simple deterministic auction algorithm that, given two matroids on a common ground set of size $n$, computes a $(1-\varepsilon)$-approximate maximum-weight common independent set using $O(n \varepsilon^{-2} \log^2(n))$ independence-oracle queries. This is the first deterministic $(1-\varepsilon)$-approximation algorithm for the weighted matroid intersection problem whose query complexity is nearly linear in $n$ and polynomial in $1/\varepsilon$. Our algorithm builds on the auction algorithm for unweighted matroid intersection by Huang--Kobayashi~['26].