A Faster Auction Algorithm for Weighted Matroid Intersection
In the authors' words
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 -approximation algorithms for this problem. We present a simple deterministic auction algorithm that, given two matroids on a common ground set of size , computes a -approximate maximum-weight common independent set using independence-oracle queries. This is the first deterministic -approximation algorithm for the weighted matroid intersection problem whose query complexity is nearly linear in and polynomial in . 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].
Appeared: Friday, October 2. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 23 pages