pipette
ESEspañol

A Faster Auction Algorithm for Weighted Matroid Intersection

Tatsuya Terao

PreprintClaims a big step

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].

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 2. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 23 pages