A Faster Auction Algorithm for Weighted Matroid Intersection
En palabras de los autores
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].
Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 23 pages