Deterministic (½ + ε )-Approximation for Submodular Maximization over a Matroid
Niv Buchbinder, Moran Feldman, Mohit Garg · Society for Industrial and Applied Mathematics eBooks · 2019
We study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves (½ + ε)-approximation for the problem. This algorithm is the first deterministic algorithm known to improve over the ½-approximation ratio of the classical greedy algorithm proved by Nemhauser, Wolsely and Fisher in 1978.