How do I go about proving that submodular maximum coverage is NP-hard?
That is, given submodular monotone function f(S), find the set of size at most K that maximizes f(S).
If f(S) is the standard coverage function (count number of distinct covered elements), then this is just the max-k-cover problem, which is NP-hard. How to prove the general case?
Thanks!