Subquadratic Weighted Matroid Intersection Under Rank Oracles
share
Given two matroids ℳ_1 = (V, ℐ_1) and ℳ_2 = (V, ℐ_2) over an n-element integer-weighted ground set V, the weighted matroid intersection problem aims to find a common independent set S^*∈ℐ_1 ∩ℐ_2 maximizing the weight of S^*. In this paper, we present a simple deterministic algorithm for weighted matroid intersection using Õ(nr^3/4logW) rank queries, where r is the size of the largest intersection of ℳ_1 and ℳ_2 and W is the maximum weight. This improves upon the best previously known Õ(nrlogW) 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.
READ FULL TEXT