Given two matroids M1 and M2 over the same n-element ground set, the matroid intersection problem is to find a largest common independent set, whose size we denote by r. We present a simple and generic auction algorithm that reduces (1 — ε)-approximate matroid intersection to roughly 1/ε2 rounds of the easier problem of finding a maximum-weight basis of a single matroid. Plugging in known primitives for this subproblem, we obtain both simpler and improved algorithms in two models of computation, including:

• The first near-linear time/independence-query (1 — ε)-approximation algorithm for matroid intersection. Our randomized algorithm uses¹ Õ (n/ε + r/ε5) independence queries, improving upon the previous   bound of Quanrud (2024).

• The first sublinear exact parallel algorithms for weighted matroid intersection, using O (n2/3) rounds of rank queries or O (n5/6) rounds of independence queries. For the unweighted case, our results improve upon the previous O (n3/4)-round rank-query and O (n7/8)-round independence-query algorithms of Blikstad (2022).

* The full version of the paper can be accessed at https://arxiv.org/abs/2410.14901

¹Throughout the paper we use Õ (·) to hide polylog n factors.