Faster Matroid Intersection

In this paper we consider the classic matroid intersection problem: given two matroids M 1 = (V, I 1 ) and M 2 = (V, I 2 ) defined over a common ground set V, compute a set S ∈ I 1 ∩ I 2 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 ∈ I i in T ind 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 M i in T rank time. In each setting we provide faster exact and approximate algorithms. Given an independence oracle, we provide an exact O(nr log r · T ind ) time algorithm. This improves upon previous best known running times of O(nr 1. 5 ·T ind ) due to Cunningham O(n 2 ·T ind in 1986 and + n 3 ) 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 O(n 1. 5 /ε 1. 5 · Tind) and O((n 2 r -1 ε -2 + r 1. 5 ε -4. 5 ) · Tind), respectively. These results improve upon the O(nr/ε · T ind )time algorithm of Cunningham (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√r log n · T rank )time exact algorithm and an O(nε -1 log n · T rank )-time algorithm which obtains a (1 - 0)-approximation to the matroid intersection problem. The former result improves over the O(nr · T rank + n 3 )-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 (via Edmond's minimax characterization of matroid intersection) of the submodular function minimization (SFM) problem with an evaluation oracle, and understanding SFM query complexity is an outstanding open question.

Authors

• Deeparnab Chakrabarty
• Yin Tat Lee
• Aaron Sidford
• Sahil Singla 0001
• Sam Chiu-wai Wong

Keywords

• Approximation algorithms
• Minimization
• Complexity theory
• Image edge detection
• Computer science
• Optimization
• Distance measurement
• Matroid Intersection
• Running Time
• Cardinality
• Estimation Algorithm
• Approximate Solution
• Exact Algorithm
• Universe
• Proof Of Theorem
• Independent Set
• Shortest Path
• Pathfinding
• Collection Of Sets
• Output Time
• Polynomial-time Algorithm
• Shortest Path Length
• Largest Set
• Maximal Set
• Binary Search
• Breadth-first Search
• Exchange Properties
• Bipartite Matching
• Fractional Solution
• Total Element
• Oracle Model
• Matroids
• Combinatorial Optimization
• Submodular Functions