TY - GEN

T1 - A fast approximation for maximum weight matroid intersection

AU - Chekuri, Chandra

AU - Quanrud, Kent

PY - 2016

Y1 - 2016

N2 - 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(nk15Q) 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 O(n2√k/og(kW)Q) 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 0{nk1.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 log2(l/ϵ)Q/ϵ2).

AB - 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(nk15Q) 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 O(n2√k/og(kW)Q) 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 0{nk1.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 log2(l/ϵ)Q/ϵ2).

UR - http://www.scopus.com/inward/record.url?scp=84962787242&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84962787242&partnerID=8YFLogxK

U2 - 10.1137/1.9781611974331.ch33

DO - 10.1137/1.9781611974331.ch33

M3 - Conference contribution

AN - SCOPUS:84962787242

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 445

EP - 457

BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

A2 - Krauthgamer, Robert

PB - Association for Computing Machinery

T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

Y2 - 10 January 2016 through 12 January 2016

ER -