Auction based methods improve matroid intersection approximations efficiently
Auction-Based Algorithms for Matroid Intersection: Near-Linear Query Complexity and Constant-Pass Semi-Streaming
Data Structures and Algorithms
Summary
Matroid intersection is a mathematical problem useful for selecting the best common elements from two overlapping groups. The authors created new auction-inspired algorithms to find very close-to-best solutions more quickly and with fewer questions asked about the data. Their approach works even when data arrives one piece at a time and uses only a small, fixed number of passes over it. This leads to more efficient and practical ways to solve complex optimization problems in various computation models.
What this means in practice
- •For large scale data engineers: Process vast datasets sequentially with limited memory using constant-pass streaming algorithms to find near-optimal common structures.
- •For optimization software developers: Implement efficient algorithms for weighted matroid intersection that reduce queries and computational overhead for improved software performance.
Authors
Chien-Chung Huang, Yusuke Kobayashi
Abstract
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.