Faster Matroid Intersection

Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-Wai Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationProceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
PublisherIEEE Computer Society
Pages1146-1168
Number of pages23
ISBN (Electronic)9781728149523
DOIs
StatePublished - Nov 2019
Event60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 - Baltimore, United States
Duration: Nov 9 2019Nov 12 2019

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2019-November
ISSN (Print)0272-5428

Conference

Conference60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019
CountryUnited States
CityBaltimore
Period11/9/1911/12/19

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Combinatorial Optimization
  • Matroids
  • Submodular Functions

Cite this

Chakrabarty, D., Tat Lee, Y., Sidford, A., Singla, S., & Chiu-Wai Wong, S. (2019). Faster Matroid Intersection. In 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