@online{Blikstad2410.14901,
TITLE = {Efficient Matroid Intersection via a Batch-Update Auction Algorithm},
AUTHOR = {Blikstad, Joakim and Tu, Ta-Wei},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2410.14901},
EPRINT = {2410.14901},
EPRINTTYPE = {arXiv},
YEAR = {2024},
MARGINALMARK = {$\bullet$},
ABSTRACT = {Given two matroids $\mathcal{M}_1$ and $\mathcal{M}_2$ over the same
$n$-element ground set, the matroid intersection problem is to find a largest
common independent set, whose size we denote by $r$. We present a simple and
generic auction algorithm that reduces $(1-\varepsilon)$-approximate matroid
intersection to roughly $1/\varepsilon^2$ rounds of the easier problem of
finding a maximum-weight basis of a single matroid. Plugging in known
primitives for this subproblem, we obtain both simpler and improved algorithms
in two models of computation, including:
* The first near-linear time/independence-query
$(1-\varepsilon)$-approximation algorithm for matroid intersection. Our
randomized algorithm uses $\tilde{O}(n/\varepsilon + r/\varepsilon^5)$
independence queries, improving upon the previous $\tilde{O}(n/\varepsilon +
r\sqrt{r}/{\varepsilon^3})$ bound of Quanrud (2024).
* The first sublinear exact parallel algorithms for weighted matroid
intersection, using $O(n^{2/3})$ rounds of rank queries or $O(n^{5/6})$ rounds
of independence queries. For the unweighted case, our results improve upon the
previous $O(n^{3/4})$-round rank-query and $O(n^{7/8})$-round
independence-query algorithms of Blikstad (2022).
},
}