Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time

Kai Han, Zongmai Cao, Shuang Cui +1

We study the problem of maximizing a non-monotone, non-negative submodular function subject to a matroid constraint. The prior best-known deterministic approximation ratio for this…