### Abstract

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 SI-1 ∩ I-2 of largest possible cardinality, denoted by r. We consider this problem both in the setting where each M-i 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 M-i 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(nr1.5⋅T-ind) due to Cunningham in 1986 and Õ(n2⋅T-ind+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 Õ(n1.5/ϵ1.5⋅T-ind) and Õ((n2r-1ϵ-2+r1.5ϵ-4.5)⋅T-ind), 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√rlog n⋅T-rank)-Time exact algorithm and an O(nϵ-1 log n⋅T-rank)-Time algorithm which obtains a (1-ϵ)-Approximation to the matroid intersection problem. The former result improves over the Õ(nr⋅T-rank+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 (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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019 |

Publisher | IEEE Computer Society |

Pages | 1146-1168 |

Number of pages | 23 |

ISBN (Electronic) | 9781728149523 |

DOIs | |

State | Published - Nov 2019 |

Event | 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 - Baltimore, United States Duration: Nov 9 2019 → Nov 12 2019 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2019-November |

ISSN (Print) | 0272-5428 |

### Conference

Conference | 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 |
---|---|

Country | United States |

City | Baltimore |

Period | 11/9/19 → 11/12/19 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

### Keywords

- Combinatorial Optimization
- Matroids
- Submodular Functions

## Cite this

*Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019*(pp. 1146-1168). [8948634] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2019-November). IEEE Computer Society. https://doi.org/10.1109/FOCS.2019.00072