# Faster Matroid Partition Algorithms

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2023.

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

- [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)

## Abstract (arXiv)

In the matroid partitioning problem, we are given k matroids M1 = (V, I1), dots , Mk = (V, Ik) defined over a common ground set V of n elements, and we need to find a partitionable set S subseteq V of largest possible cardinality, denoted by p. Here, a set S subseteq V is called partitionable if there exists a partition (S1, dots , Sk) of S with Si ∈ Ii for i = 1, ldots, k. In 1986, Cunningham [SICOMP 1986] presented a matroid partition algorithm that uses O(n p3/2 + k n) independence oracle queries, which was the previously known best algorithm. This query complexity is O(n5/2) when k ≤ n. Our main result is to present a matroid partition algorithm that uses tildeO(k'1/3 n p + k n) independence oracle queries, where k' = mink, p. This query complexity is tildeO(n7/3) when k ≤ n, and this improves upon the one of previous Cunningham's algorithm. To obtain this, we present a new approach edge recycling augmentation, which can be attained through new ideas: an efficient utilization of the binary search technique by Nguyen [2019] and Chakrabarty-Lee-Sidford-Singla-Wong [FOCS 2019] and a careful analysis of the independence oracle query complexity. Our analysis differs significantly from the one for matroid intersection algorithms, because of the parameter k. We also present a matroid partition algorithm that uses tildeO((n + k) √p) rank oracle queries.