Source-linked AI summary
A Faster Auction Algorithm for Weighted Matroid Intersection
Tatsuya Terao
TL;DR
Weighted matroid intersection asks for a maximum-weight common independent set, and earlier work left open a deterministic nearly linear-query approach with polynomial dependence on 1/ε. This paper adapts an unweighted auction algorithm to the weighted problem. It gives a deterministic (1−ε)-approximation using O(nε^-2 log^2(n)) independence-oracle queries.
Problem
It was unknown whether an unweighted auction algorithm could extend directly to weighted matroid intersection with nearly linear independence-oracle queries and polynomial dependence on 1/ε.
Source: §1.2 · p. 3Method
The paper presents a deterministic auction algorithm for weighted matroid intersection based on Huang–Kobayashi’s [HK26] unweighted auction algorithm.
Source: §1.2 · pp. 2–3Results
O(nε^-2 log^2(n)) independence-oracle queries yield a deterministic (1−ε)-approximation for weighted matroid intersection.
Source: §1.2 · p. 3Takeaways & Limitations
The algorithm is the first deterministic (1−ε)-approximation for weighted matroid intersection with nearly linear query complexity in n and polynomial dependence on 1/ε.
Source: §1.2 · p. 3The paper assumes that each matroid is accessed through an independence oracle.
Source: §2.1 · p. 4
Abstract
from arXiv · showhide
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].
1 Introduction
Weighted matroid intersection seeks a maximum-weight set independent in both matroids, with independence-oracle query complexity a central efficiency measure. This paper presents a deterministic auction algorithm with a nearly linear-in-n query bound and polynomial dependence on 1/ε.
1 Introduction
- The problem generalizes classical optimization problems, including bipartite matching, and asks for a maximum-weight common independent set.An independence oracle determines whether a queried set is independent.Source: §1 · p. 1
1.1 Previous Work
- Earlier weighted approximation algorithms had rank-dependent query bounds, while Dudeja–Grilnberger [DG26] gave a reduction with ε−O(1/ε) dependence.The reduction combines an unweighted approximation algorithm with a weight-aspect-ratio factor.Source: §1.1 · p. 2
1.2 Our Result
- O(nε^-2 log^2(n)) independence-oracle queries suffice for a deterministic (1−ε)-approximation, the first such weighted algorithm with nearly linear dependence on n and polynomial dependence on 1/ε.The algorithm builds on Huang–Kobayashi [HK26] for unweighted matroid intersection.Source: §1.2 · p. 3
- Prior work left open whether an unweighted auction algorithm could extend directly to weighted matroid intersection with nearly linear oracle queries and polynomial dependence on 1/ε.The paper identifies both questions as motivation for its algorithm.Source: §1.2 · p. 3
2 Preliminary
The preliminaries set the weighted matroid intersection objective and establish notation and matroid facts used by the algorithm. They also specify the independence-oracle model and the approximation target.
2.1 Notation
- A matroid’s inclusion-wise maximal independent sets are bases, its inclusion-wise minimal dependent sets are circuits, and its bases satisfy simultaneous exchange.For bases B1 and B2 and e in B1\B2, some f in B2\B1 makes both B1−e+f and B2+e−f bases.Source: §2.1 · p. 3
- The goal is to find a common independent set of weight at least (1−ε)·w(OPTw), where OPTw is a maximum-weight common independent set.The ground set has n elements, and the paper assumes independence-oracle access to each matroid.Source: §2.1 · p. 4
2.2 Basic Properties
- A q-maximum independent set is characterized by nonpositive addable outside weights, nonnegative inside weights, and no improving feasible one-for-one exchange.These three conditions are the stated necessary and sufficient conditions for w-maximum independence.Source: §2.2 · p. 4
- With O(log |R|) independence queries, binary search finds the minimum-weight removable element from R that preserves independence after adding v, when one exists.The search applies when S is independent, R⊆S, and v is outside S.Source: §2.2 · p. 5
- If Y lies in a q-maximum base, adding e preserves that possibility exactly when a base exchange can replace an element outside Y with equal q-value.The exchanged element may be e itself.Source: §2.2 · p. 5
3 The Algorithm
The algorithm maintains a common independent set and prices, using rounded utilities to guide additions and exchanges. Each round scans unselected elements, adds eligible ones, and removes a cheapest conflicting element when needed to preserve independence.
3.1 Prices and Utilities
- The price p(e) adds εw(e) to the minimum price of an item that must be removed to add e, or to zero when e is directly addable in M2.For a conflicting addition, the minimum is taken over elements in the fundamental circuit that can be removed while preserving independence.Source: §3.1 · p. 5
- The utility q(e) is the rounded value of w(e)−p(e), and the rounding uses powers of 1+ε so decreases between distinct positive levels are by at least a factor of 1+ε.The paper uses this rounding property in the analysis of M1.Source: §3.1 · pp. 5–6
3.2 Algorithm Description
- The algorithm returns the heaviest set among the sets at the ends of rounds, while the round-start state remains fixed during each round.The algorithm denotes the end-of-round set by X_t.Source: §3.1 · p. 7, §3.2 · p. 7
- Within each round, the algorithm scans each element outside the round-start set once and adds it when its positive utility is unchanged and it can belong to a q*-maximum base of M1.If adding it violates independence in M2, the algorithm removes a cheapest element from the relevant fundamental circuit.Source: §3.2 · p. 7
4 Analysis
The analysis establishes auction invariants, bounds the optimum through weight splitting, and controls progress across rounds to prove a (1−3ε)-approximation; it concludes by establishing m<T.
4.1 Useful Properties
- Throughout execution, X remains independent in M2, its elements’ prices lie between εw(e) and w(e), and prices never decrease while utilities never increase.The algorithm also preserves its base-related invariants: Y stays within a q*-maximum base, and X is contained in a q-maximum base at each round’s start.Source: §4.1 · pp. 8–9
4.2 Weight-Splitting Argument
- At every point, U(X, π) ≥ (1−ε)w(OPTw), by bounding the optimum’s price and utility contributions separately.The argument combines bounds on ¯p(OPTw) and q(OPTw), using ¯p(e)+q(e) ≥ (1−ε)w(e).Source: §4.2 · pp. 9–10
4.3 Progress in One Round
- At a round’s end, any e outside Y whose addition remains in a q*-maximum base has q′(e) ≤ q*(e)/(1+ε).This bound supplies the utility-decay condition used to control the change in U over one round.Source: §4.3 · p. 10
4.4 Approximation Ratio
- The final set X_m is a common independent set, and its price π(X_m) is at most opt, since π(X_m) ≤ w(X_m) ≤ opt.Source: §4.4 · p. 13
- For 0<ε<1/3, the analysis uses log(1+ε)≥ε/2, log(1/ε)<1/ε, and 2(1+ε)/ε<3/ε.Source: §4.4 · p. 13
- The proof concludes with m<T.Source: §4.4 · p. 13
5 Query Complexity
The section bounds the query cost of each round and derives the total independence-query complexity from the number of rounds. It implements the per-round scan with logarithmic-query procedures for testing and element values.
5 Query Complexity
- Given X and π, computing an element’s price and utility takes O(log r) queries, using a minimum-price exchange element when X + e is dependent in M2.The exchange element is found by binary search; q(e) is obtained from p(e).Source: §5 · p. 14
- Round initialization computes q* for all elements and builds a q*-maximum base containing X* with a greedy scan.Computing q* uses O(n log r) queries, and the scan adds n more queries.Source: §5 · p. 14
- Each round uses O(n log r) independence queries because it scans at most n elements, using O(log r) queries per element.The scan tests whether an element can be added while preserving containment in a q*-maximum base.Source: §5 · p. 14
- O(n log r · (ε^-1 log r + ε^-2)) total queries, plus O(n) preprocessing, follows from the round count and per-round implementation bound.The round count is O(ε^-1 log r + ε^-2), and each round uses O(n log r) queries.Source: §5 · pp. 13–14