Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid
Niv Buchbinder, Moran Feldman, Mohit Garg · SIAM Journal on Computing · 2023
Abstract. We study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves [Formula: see text]-approximation for the problem (for some [Formula: see text]). This algorithm is the first deterministic algorithm known to improve over the [Formula: see text]-approximation ratio of the classical greedy algorithm proved by Nemhauser, Wolsey, and Fisher in 1978.