A Faster Auction Algorithm for Weighted Matroid Intersection
The paper presents a simple deterministic auction algorithm for weighted matroid intersection that finds a (1-ε)-approximate maximum-weight common independent set. It achieves this using O(nε^-2 log^2(n)) independence-oracle queries, which is nearly linear in the ground set size n and polynomial in 1/ε. This is the first such deterministic algorithm with these query complexity bounds.