5
$\begingroup$

Let $f(X)$ be a monotone submodular function from $2^{\{1, \ldots, n\}}$ to $\mathbb{N}$ and consider the problem of maximizing it subject to a cardinality constraint $|X| \leq m$. By using the greedy algorithm, it is possible to obtain a $1-1/e$ approximation (see, for example, these lecture notes).

But now suppose $f_1(X), \ldots, f_k(X)$ are monotone submodular functions and we want to maximize $\min(f_1(X), \ldots, f_k(X))$ subject to the same cardinality constraint. Is it still possible to obtain a constant factor approximation?

$\endgroup$
3
$\begingroup$

Krause, McMahan, Guestrin and Gupta, who call this problem Robust Submodular Observation Selection show that is is NP-hard to approximate this problem to within any constant.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.