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