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?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.