A fast approximation for maximum weight matroid intersection

Chandra Chekuri, Kent Quanrud

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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).

Original languageEnglish (US)
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
EditorsRobert Krauthgamer
PublisherAssociation for Computing Machinery
Pages445-457
Number of pages13
ISBN (Electronic)9781510819672
StatePublished - Jan 1 2016
Event27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States
Duration: Jan 10 2016Jan 12 2016

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume1

Other

Other27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
CountryUnited States
CityArlington
Period1/10/161/12/16

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A fast approximation for maximum weight matroid intersection'. Together they form a unique fingerprint.

Cite this