Weighted matroid intersection solved faster with simple auction method
A Faster Auction Algorithm for Weighted Matroid Intersection
Data Structures and Algorithms
Summary
This paper tackles a complex problem called weighted matroid intersection, which involves finding the best shared structure from two sets. The authors present a straightforward method inspired by auction ideas that quickly approximates the best solution. Their approach significantly reduces the number of queries needed to achieve a near-best answer compared to earlier methods. This improvement is deterministic, meaning it gives consistent results every time.
What this means in practice
- •For network designers: Compute near-optimal shared resource allocations quickly when combining multiple connection policies represented as matroids.
- •For supply chain planners: Approximate best combined selections of suppliers or routes under multiple constraints represented by matroids more efficiently.
Authors
Tatsuya Terao
Abstract
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], together with the analysis of the auction algorithm for weighted bipartite matching by Liu--Ke--Khuller [APPROX'23].