A Fast Approximation for Maximum Weight Matroid Intersection
Chandra Chekuri, Kent Quanrud · 2015
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(nk1.5Q) time. For the weighted case, algorithms due to Frank and Brezovec et al. run in O(nk2Q) time. There are also scaling based algorithms that run in time, where W is the maximum weight (assuming all weights are integers), and ellipsoid-style algorithms that run in O((n2 log(n)Q + n3 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 O(nk1.5 log(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 log2 (1/∊)Q/∊2).