A fast approximation for maximum weight matroid intersection

We present an approximation algorithm for the maximum weight matroid intersection problem in the independence oracle model. Given two matroids defined over a common ground set N of n elements, let k be the rank of the matroid intersection and let Q denote the cost of an independence query for either matroid. An exact algorithm for finding a maximum cardinality independent set (the unweighted case), due to Cunningham, runs in O(nk¹⁵Q) time. For the weighted case, algorithms due to Frank and Brezovec et al. run in O(nk²Q) time. There are also scaling based algorithms that run in O(n²√k/og(kW)Q) time, where W is the maximum weight (assuming all weights are integers), and ellipsoid-style algorithms that run in O((n² log(n)Q + n³ polylog(n)) log(nW)) time. Recently, Huang, Kakimura, and Kamiyama described an algorithm that gives a (1 - ϵ)-approximation for the weighted matroid intersection problem in 0{nk^1.5log(k)Q/ϵ) time. We observe that a (1 - ϵ)-approximation for the maximum cardinality case can be obtained in O(nkQ/ϵ) time by terminating Cunningham's algorithm early. Our main contribution is a (1-ϵ) approximation algorithm for the weighted matroid intersection problem with running time O(nk log²(l/ϵ)Q/ϵ²).