Source-linked AI summary
Auction-Based Algorithms for Matroid Intersection: Near-Linear Query Complexity and Constant-Pass Semi-Streaming
Chien-Chung Huang, Yusuke Kobayashi
TL;DR
Matroid intersection asks for a largest common independent set, and approximation algorithms must work efficiently with oracle access to the matroids. This paper adapts auction algorithms through a stable-matching framework to obtain deterministic approximations with near-linear query bounds and a constant-pass semi-streaming result.
Problem
The problem is to find a common independent set of size at least (1−ε) times the maximum size for two matroids.
Source: §2.1 · p. 7Method
The algorithms use an auction framework connected to stable matching with matroid constraints.
Source: §1.3 · p. 5Results
O(n log n/ε) rank queries yield deterministic (1−ε)-approximations for unweighted and weighted problems, while the semi-streaming algorithm also gives a deterministic near-linear-query offline result.
Source: §1.2 · p. 4Takeaways & Limitations
The auction approach improves approximation algorithms across rank-oracle, weighted, and semi-streaming settings.
Source: §6 · p. 26The weighted result uses a reduction; extending the semi-streaming algorithm directly to the weighted setting remains open.
Source: §6 · p. 26
Abstract
from arXiv · showhide
In this paper, we develop a new auction-based framework for matroid intersection and use it to obtain improved approximation algorithms in several computational settings. Our framework is inspired by Fleiner's generalized stable matching algorithm and extends the semi-streaming auction algorithm for bipartite matching due to Assadi, Liu, and Tarjan. Using this framework, for any $\varepsilon > 0$, we present a simple $(1-\varepsilon)$-approximation algorithm in the rank-oracle model whose query complexity matches that of the current fastest algorithm. Furthermore, by extending this result, we obtain the first $(1-\varepsilon)$-approximation algorithm for the weighted problem that requires only a near-linear number of rank-oracle queries, achieving the best known rank-oracle query complexity for the problem. We also obtain a $(1-\varepsilon)$-approximation semi-streaming algorithm for matroid intersection in the multi-pass streaming model, where the elements of the ground set arrive sequentially. It is the first algorithm achieving this approximation ratio using a constant number of passes and nearly linear space in the ranks of the matroids. When viewed in the standard offline setting, the same algorithm yields the first deterministic $(1-\varepsilon)$-approximation algorithm for matroid intersection that requires only a near-linear number of independence-oracle queries.
1 Introduction
Matroid intersection seeks a largest set independent in two matroids, accessed through oracles because explicitly storing their independent sets is prohibitively expensive. The paper introduces auction-based algorithms that improve approximation guarantees across rank-oracle and semi-streaming settings.
1.1 Previous Work
- Earlier near-linear independence-query approximation for the unweighted problem was randomized, weighted reductions incurred weight-range-dependent query overhead, and prior constant-pass streaming achieved only (2/3−ε).The prior (1−ε) semi-streaming algorithm cited here required O(log n/ε) passes.Source: §1.1 · pp. 2–3
1.2 Our Contributions
- O(n log n/ε) rank queries suffice for deterministic (1−ε)-approximation algorithms for both unweighted and weighted matroid intersection.The unweighted algorithm matches the fastest known rank-query complexity; the weighted result is the first near-linear rank-query algorithm for that problem.Source: §1.2 · p. 4
- The semi-streaming algorithm is the first to achieve a (1−ε)-approximation with a constant number of passes and nearly linear space in the matroid ranks.It is deterministic and also gives the first deterministic (1−ε)-approximation with near-linear independence queries in the offline setting.Source: §1.2 · p. 4
- For bipartite matching, the algorithm improves space from O(r′) to O(r) by truncating the partition matroids to rank O(r).Here r is the maximum common independent-set size, while r′ is the number of graph vertices.Source: §1.2 · p. 5
1.3 Our Technique
- The framework adapts Assadi, Liu, and Tarjan’s auction algorithm through Fleiner’s stable-matching-with-matroid-constraints framework.An implicit price representation stores prices only for elements provisionally held, reducing the semi-streaming algorithm’s space requirement.Source: §1.3 · pp. 5–6
2 Preliminary
This section establishes notation and assumptions for matroid optimization, then gives basic properties used by the algorithms. It also describes a binary-search technique for reducing oracle queries and a local criterion for maximum-weight independent sets.
2.1 Notation
- The paper models matroids through independent sets, bases, circuits, rank, span, and weight-minimizing or weight-maximizing sets.A base is an inclusion-wise maximal independent set; a fundamental circuit is the unique circuit in X + e when that set is dependent.Source: §2.1 · pp. 6–7
- For two matroids on a finite ground set of size n, the goal is a common independent set of size at least (1 − ε)r, where r is the maximum common-independent-set size and ε > 0.Each matroid is given by oracles; throughout, 1/ε is an integer with 1/ε ≤ n + 1, and both matroids have no loops.Source: §2.1 · p. 7
2.2 Basic Properties
- For dependent X + e, removing f restores independence exactly when f belongs to the fundamental circuit of X and e.The lemma also states that raising prices outside a set S preserves S’s containment in a minimum-price base, provided S was contained in one before.Source: §2.2 · p. 7
- An independent set is weight-maximum exactly when no feasible addition or exchange improves it, and its included elements have nonnegative weight.This local-neighbor criterion is used to certify maximum-weight independent sets.Source: §2.2 · p. 8
- The binary-search technique finds a minimum-weight feasible addition using O(log |E \ S|) rank queries, or a minimum-weight element of T using O(log |T|) independence queries.It applies to an independent set S, a subset T of S, an outside element v, and a weight function.Source: §2.2 · p. 8
3 Simple Algorithm with Nearly Linear Rank Queries
The section presents an auction algorithm that adjusts element prices while maintaining a common independent set. It proves a deterministic (1 − ε)-approximation with O(n log n/ε) rank queries and relates the output to generalized stable matching.
3 Simple Algorithm with Nearly Linear Rank Queries
- Alice adds affordable elements to X; when Bob cannot accept an addition under M2, he removes the cheapest circuit element and raises its price by ε.Prices increase monotonically, and X represents the items provisionally agreed for trade.Source: §3 · p. 8
3.1 Query Complexity
- Algorithm 1 uses O(n log n/ε) rank queries, with at most r addition attempts and O(n/ε) price-update iterations.The proof bounds loop executions and implements selection steps with logarithmically many oracle queries.Source: §3.1 · p. 9
3.2 Key Invariants
- At each loop iteration, X remains contained in a p-minimum base of M1, supporting the algorithm’s approximation proof.The algorithm also maintains a price-based invariant for elements outside X, stated in Lemma 3.5.Source: §3.2 · p. 10
3.3 Proof for Theorem 1.1
- A deterministic (1 − ε)-approximation for matroid intersection uses O(n log n/ε) rank queries.The algorithm returns a common independent set of size at least (1 − ε)r.Source: §3.3 · pp. 11–12
3.4 Relation to Generalized Stable Matching
- The output induces a stable set in a constructed two-agent market with matroid constraints and opposing price preferences.The paper says this connection is conceptually informative but does not directly improve algorithmic performance.Source: §3.4 · pp. 12–13
4 Weighted Problem with Nearly Linear Rank Queries
The section extends the auction algorithm to weighted matroid intersection by treating weights as valuations and adjusting prices by weight-scaled increments. It proves a deterministic (1 − ε)-approximation using O(n log n/ε) rank queries.
4 Weighted Problem with Nearly Linear Rank Queries
- The weighted algorithm defines q(e) = w(e) − p(e) as Alice’s utility and increases a removed element’s price by εw(f).It chooses an eligible element maximizing q(e), rather than minimizing p(e).Source: §4 · pp. 13–14
- Algorithm 2 uses O(n log n/ε) rank queries.Its analysis adapts the unweighted algorithm’s observations and lemmas.Source: §4 · p. 14
- A deterministic (1 − ε)-approximation for weighted matroid intersection uses O(n log n/ε) rank queries.The returned common independent set X satisfies w(X) ≥ (1 − ε)w(OPTw).Source: §4 · pp. 14–15
- The proof compares X with OPTw using q-maximum and p′-maximum independent-set properties in M1 and M2, respectively.Those comparisons establish the weighted approximation guarantee.Source: §4 · p. 15
5 Semi-Streaming Algorithm
This section develops and analyzes a semi-streaming auction algorithm that maintains a common independent set and element prices. It refines the algorithm to achieve a (1−ε)-size guarantee with a deterministic implementation under bounded passes, space, and independence queries.
5.1 Algorithm Description
- The auction stores prices only for elements in X, processes arriving elements sequentially while preserving M2 independence, and repeats its superset-replacement round only 2/ε^2 times.Source: §5.1 · p. 16
5.2 Useful Properties
- During each inner-loop iteration, X remains contained in a p-minimum base of M1, Y in a p*-minimum base, and induced prices are nondecreasing.Source: §5.2 · pp. 17, 19
5.3 Potential Functions and Approximation Ratio
- Algorithm 3 returns a common independent set X with |X| ≥ (1 - 2ε)r.Source: §5.3 · p. 22
- Replacing ε with ε/2 gives an output set X of size at least (1−ε)r.The approximation analysis uses the bounded increase of the item and buyer potentials across the algorithm’s rounds.Source: §5.3 · p. 23
5.4 Refined Implementation
- Algorithm 4 maintains a p*-minimum base Z of M1 containing Y, using an equal-price exchange to test whether Y+e can be included in such a base.This avoids the additional streaming pass that a naive check would require and makes Algorithm 4 behave like Algorithm 3.Source: §5.4 · pp. 23–24
5.5 Query Complexity and Number of Passes
- The algorithm computes p(e) with O(log r) independence queries and constructs a p*-minimum base containing Y in one streaming pass using O(n log r) independence queries.The base is built greedily, adding feasible elements or exchanging an element outside Y when needed.Source: §5.5 · pp. 24–25
- Algorithm 4 is deterministic and uses O(1/ε^2) passes, O(r) space, and O(n log r/ε^2) independence queries.These bounds, together with Proposition 5.10, prove Theorem 1.3.Source: §5.4 · p. 24, §5.5 · p. 26
6 Concluding Remarks
The paper proposes auction-based algorithms for matroid intersection and extends one result to the weighted setting via a reduction. Directly extending Algorithm 3 to the weighted setting remains an open question, as do further improvements in passes, space, and queries.
6 Concluding Remarks
- The paper proposes auction-based algorithms for matroid intersection and obtains improved approximation algorithms in several computational settings.Source: §6 · p. 26
- Further reducing the number of passes, space complexity, and query complexity is identified as future work.Source: §6 · p. 26
- The weighted extension uses the reduction of Dudeja and Grilnberger [18], while extending Algorithm 3 more directly remains open.Source: §6 · p. 26