arXiv:2610.00920 · v3
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-\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].
作者备注：17 pages. In this version, we have completely rewritten the proof, which is now simpler and easier to follow, and improved the clarity and presentation of the paper. We plan to combine this work with that of Huang and Kobayashi (arXiv:2609.38685) in a future version, providing a more polished and unified presentation