A Faster Auction Algorithm for Weighted Matroid Intersection

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-\epsilon )$-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-\epsilon )$-approximate maximum-weight common independent set using $O(n{\epsilon }^{-2}{\log }^2(n))$ independence-oracle queries. This is the first deterministic $(1-\epsilon )$-approximation algorithm for the weighted matroid intersection problem whose query complexity is nearly linear in $n$ and polynomial in $1\mathrm{/}\epsilon$. Our algorithm builds on the auction algorithm for unweighted matroid intersection by Huang–Kobayashi ['26], together with the analysis of the auction algorithm for weighted bipartite matching by Liu–Ke–Khuller [APPROX’23].