# NP-hardness of maximum set cover with element-level submodular function

Consider the following generalization of maximum set cover problem:

Given a collection $C$ of subsets of a finite set $S$.

Find $C^{'} \subseteq C$ of cardinality $k$ that maximizes

$\sum\limits_{s \in S} f(s, C^{'})$

For example:

If $f(s, C^{'})=\begin{cases}1 & \exists c \in C^{'}, s \in c \\ 0 & \text{otherwise}\end{cases}$,

the problem is essentially maximum set cover and it's NP-hard.

However, if $f(s, \cdot)$ is submodular function, for example:

$f(s, C^{'})= \frac{|\{c \in C^{'} \mid s \in c \}| -1}{|\{c \in C^{'} \mid s \in c \}|}$

Is the problem still NP-hard?

• Your example of a submodular function isn't defined if $s \not in c$ for all $c \in C'$ (divide-by-zero error). – D.W. Dec 9 '17 at 16:55