The problem of unconstrained submodular maximization can be phrased as follows:

Given a non-negative submodular function $f$ on a domain $D$ find a set $S \subseteq D$ maximizing $f(S)$.

Here a submodular function is one satisfying $$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B) $$ for all $A,B \subseteq D$.

Buchbinder et al. gave a $1/2$-approximation algorithm for this problem. This is best possible in the value oracle model: Feige et al. showed that achieving a $(1/2+\epsilon)$-approximation requires exponentially many value oracle queries, for any $\epsilon > 0$.

What if the function $f$ is given explicitly? Dobzinsky and Vondrák gave a class of explicit functions for which no $(1/2+\epsilon)$-approximation can be achieved unless $\mathsf{NP} = \mathsf{RP}$.

My question is:

Is there a natural class of explicit submodular functions that is NP-hard to $(1/2+\epsilon)$-approximate for all $\epsilon > 0$?

Compared to Dobzinsky and Vondrák's result, I want a result which holds under the assumption $\mathsf{NP} \neq \mathsf{P}$ rather than the stronger $\mathsf{NP} \neq \mathsf{RP}$, and moreover I want the class of explicit functions to be natural, in contrast to the ingenious but somewhat contrived functions used by Dobzinsky and Vondrák.

For the related problem of monotone submodular maximization subject to a matroid constraint, such a beast does exist: Feige famously showed that is it NP-hard to approximate Maximum Coverage any better than $1-1/e$, which matches both the value oracle hardness and the best approximation algorithms.

  • 4
    $\begingroup$ Is there a natural class for which we have a weaker but still meaningful bound? Say a class for which we cannot get better than $2/3$-approximation? $\endgroup$ – Chandra Chekuri May 20 '16 at 20:59

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.