Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint

Yuval Filmus, Roy Schwartz, Alexander V. Smal

We consider two classic problems: maximum coverage and monotone submodular maximization subject to a cardinality constraint. [Nemhauser--Wolsey--Fisher '78] proved that the greedy…