Title: Monotone Submodular Maximization over a Matroid
Speaker: Yuval Filmus, IAS
Date: Wednesday, April 16, 2014 11:00-12:00pm
Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Maximizing a monotone submodular function over the bases of a matroid is a fundamental algorithmic question, which generalizes the well-known NP-complete problem MaxCover. A few years ago, Calinescu, Chekuri, Pál and Vondrák developed a sophisticated algorithm for the problem, the continuous greedy algorithm, which attains the optimal approximation ratio 1-1/e. Their algorithm combines a Frank--Wolfe phase together with lossless rounding. We offer an alternative algorithm attaining the same approximation ratio. Our algorithm is based on a neglected algorithmic paradigm, non-oblivious local search, in which local search is run with respect to an auxiliary objective function. Our auxiliary objective function is also monotone and submodular, and satisfies the following property: a local optimum with respect to the auxiliary objective function is a (1-1/e)-approximate *global* optimum with respect to the original objective function.
Joint work with Justin Ward (University of Warwick).
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/