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^{ *} \in \mathcal{ I}_1 \cap \mathcal{ I}_2$ maximizing the weight of $S^{ *}$. In this paper, we present a simple deterministic algorithm for weighted matroid intersection using $\tilde{ O}(nr^{ 3/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.
Categories: cs.DS