Subquadratic Weighted Matroid Intersection Under Rank Oracles

Given two matroids ${\mathcal{M}}_1=(V,{\mathcal{I}}_1)$ and ${\mathcal{M}}_2=(V,{\mathcal{I}}_2)$ over an $n$-element integer-weighted ground set $V$, the weighted matroid intersection problem aims to find a common independent set $S^{\ast }\in {\mathcal{I}}_1\cap {\mathcal{I}}_2$ maximizing the weight of $S^{\ast }$. In this paper, we present a simple deterministic algorithm for weighted matroid intersection using $\tilde{O}(n{r}^{3\mathrm{/}4}\log W)$ rank queries, where $r$ is the size of the largest intersection of ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$ and $W$ is the maximum weight. This improves upon the best previously known $\tilde{O}(nr\log W)$ algorithm given by Lee, Sidford, and Wong [FOCS’15], and is the first subquadratic algorithm for polynomially-bounded weights under the standard independence or rank oracle models. The main contribution of this paper is an efficient algorithm that computes shortest-path trees in weighted exchange graphs.