1
$\begingroup$

Maximizing a monotone submodular function with a cardinality constraint can be solved by using a simple greedy heuristic. However, if the submodular function is non-monotone, the greedy heuristic can perform arbitrarily poorly.

Now I have a very special non-monotone submodular function: $$G(S)=F(S)−a|S|,\qquad S\subseteq V$$ where $F(S)$ is monontone submodular, $a$ is a constant. Furthermore, $G(S)≥0,G(\emptyset)=G(V)=0$.

Does the greedy heuristic still perform poorly for problem $\max_{|S|\leq K}G(S)$?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.