Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid

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.

Authors

• Niv Buchbinder
• Moran Feldman
• Mohit Garg 0003

Keywords

• Submodular optimization
• matroid
• deterministic algorithms