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 1. 5 Q ) time. For the weighted case, algorithms due to Frank and Brezovec et al. run in O ( nk 2 Q ) 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 (( n 2 log( n )Q + n 3 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 ( nk 1. 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 log 2 (1/∊) Q /∊ 2 ).

Authors

• Chandra Chekuri
• Kent Quanrud

Keywords

No keywords are indexed for this paper.