Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid

07/15/2018

∙

by   Niv Buchbinder, et al.

∙

0

∙

share

We study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves (1/2 + ϵ)-approximation for the problem. This algorithm is the first deterministic algorithm known to improve over the 1/2-approximation ratio of the classical greedy algorithm proved by Nemhauser, Wolsely and Fisher in 1978.