Faster Matroid Intersection

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.