DETERMINISTIC (1/2+ϵ)-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 (1/2+ϵ)-approximation for the problem (for some ϵ ≥ 8 10-4). This algorithm is the first deterministic algorithm known to improve over the 1/2-approximation ratio of the classical greedy algorithm proved by Nemhauser, Wolsey, and Fisher in 1978.