# Faster Matroid Intersection

arXiv: https://arxiv.org/abs/1911.10765 · HTML: https://mlsanity.com/paper/1911.10765/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2019.

## Built on by (most cited first, 6 of 6)

- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations](https://mlsanity.com/paper/2206.08495/) (2022)
- [Streaming Algorithms for Diversity Maximization with Fairness Constraints](https://mlsanity.com/paper/2208.00194/) (2022)
- [Accelerating Matroid Optimization through Fast Imprecise Oracles](https://mlsanity.com/paper/2402.02774/) (2024)
- [Multilevel Fair Allocation with Matroid-Rank Preferences](https://mlsanity.com/paper/2512.24105/) (2025)
- [Matroid Algorithms Under Size-Sensitive Independence Oracles](https://mlsanity.com/paper/2605.00201/) (2026)

## Abstract (arXiv)

In this paper we consider the classic matroid intersection problem: given two matroids M1=(V,I1) and M2=(V,I2) defined over a common ground set V, compute a set S∈I1capI2 of largest possible cardinality, denoted by r. We consider this problem both in the setting where each Mi is accessed through an independence oracle, i.e. a routine which returns whether or not a set S∈Ii in indep time, and the setting where each Mi is accessed through a rank oracle, i.e. a routine which returns the size of the largest independent subset of S in Mi in rank time. In each setting we provide faster exact and approximate algorithms. Given an independence oracle, we provide an exact O(nrlog r indep) time algorithm. This improves upon the running time of O(nr1.5 indep) due to Cunningham in 1986 and tildeO(n2 indep+n3) due to Lee, Sidford, and Wong in 2015. We also provide two algorithms which compute a (1-ε)-approximate solution to matroid intersection running in times tildeO(n1.5/eps1.5 indep) and tildeO((n2r-1ε-2+r1.5ε-4.5) indep), respectively. These results improve upon the O(nr/eps indep)-time algorithm of Cunningham as noted recently by Chekuri and Quanrud. Given a rank oracle, we provide algorithms with even better dependence on n and r. We provide an O(n√rlog n rank)-time exact algorithm and an O(nε-1log n rank)-time algorithm which obtains a (1-eps)-approximation to the matroid intersection problem. The former result improves over the tildeO(nr rankt+n3)-time algorithm by Lee, Sidford, and Wong. The rank oracle is of particular interest as the matroid intersection problem with this oracle is a special case of the submodular function minimization problem with an evaluation oracle.