Does any approximation algorithm exist for maximization non-monotone submodular functions that might have negative values or be unbounded below?

Fact 1: For monotone submodular functions, Nemhauser, Wolsey and Fisher proved [1] that simple greedy algorithm gives $1-1/e$ approximation guarantee.

Fact 2: For non-monotone non-negative submodular functions, Buchbinder et. all proved [2] that randomized greedy algorithm gives $1/e$ approximation for cardinality constraint.


Edit: See my answer to the same question on math stackexchange here. I've copy and pasted the answer again for ease of use.

There has been a recent line of work investigating algorithms for submodular optimization problems when the objective may take negative values. So far, the non-negativity that we can handle is when the submodular objective decomposes into the sum of a monotone submodular and an arbitrary modular function. The optimization problem is $$ \max_{S \in \mathcal{I}} g(S) - c(S) \enspace,$$ where $g:2^V \rightarrow \mathbb{R}_+$ is a non-negative and monotone submodular function, $c:2^V \rightarrow \mathbb{R}$ is a modular function, and $\mathcal{I} \subset 2^V$ is a matroid on the ground set $V$. Note that if $c$ takes positive values, then the entire submodular objective $f = g - c$ is non-monotone and may take negative values. The first approximation result was given by Sviridenko, Vondrák, and Ward in 2014 who showed that one can use a continuous extension & rounding approach to obtain a set $S$ such that $$ g(S) - c(S) \geq (1 - e^{-1}) g(OPT) - c(OPT) $$ They applied this result to obtain tight approximation guarantees for monotone submodular maximization and monotone supermodular minimization with bounded curvature. They also show that this approximation is tight in the sense that no algorithm making polynomially many queries to $g$ and $c$ can do better. Then in 2018, Feldman gave an algorithm that also goes through the continuous domain but is more efficient in that it by-passes a certain "guessing step" in the previous algorithm. Most recently, Harshaw, Feldman, Karbasi, and Ward in 2019 gave a series of much faster algorithms which do not go through the continuous extension, but are based on greedily optimizing a "distorted surrogate objective" which changes thoroughout the algorithm; however, their results apply only when the modular function is non-negative and the constraint is a cardinality constraint. They also extend the analysis to show that when $g$ is $\gamma$-weakly submodular, then one may obtain the analogous approximation $$ g(S) - c(S) \geq (1 - e^{-\gamma}) g(OPT) - c(OPT) $$ Moreover, this extended approximation guarantee is tight in the value oracle model.

There is the hardness result by Uriel Feige which shows that even verifying that $f(S) \geq 0$ for some $S$ is NP-Hard. So, the decomposition into a sum of submodular and monotone functions really is crucial in all these algorithms. I don't know how much further one can push the decomposition approach.

| cite | improve this answer | |
  • $\begingroup$ Nice answer, and welcome to CS.SE! I hope you'll stick around! $\endgroup$ – D.W. May 6 '19 at 17:04

The notion of approximation isn't well-defined when outputs are signed. If the correct answer is $1$ and the algorithm returned $-1$, what is the corresponding approximation ratio? It's not clear. This is why we want our functions to be non-negative.

That said, if $f$ is submodular then $f+C$ is submodular for all $C$. This means that you can shift your function to be non-negative, run one of the algorithm you mentioned, then shift back. You'll have to work out what guarantees you get. In fact, for the algorithms you mention you don't even need the shift, since shifting everything by a constant doesn't change the way they work at all.

| cite | improve this answer | |
  • $\begingroup$ You're absolutely right about ambiguity of notion of approximation for negative numbers and adding by a constant. 1- What if we define the notion of approximation by $\frac{S - \phi}{OPT - \phi}$? (where S is solution given by algorithm and OPT is optimal solution) $\endgroup$ – James Mar 25 '16 at 11:22
  • $\begingroup$ What is $\phi$? And what do you think happens, given what you already know? $\endgroup$ – Yuval Filmus Mar 25 '16 at 13:37
  • $\begingroup$ By $\phi$, I meant to say empty set ($\emptyset$). I was wondering if we can have a approximation guarantee in the form of $\frac{S-\emptyset}{OPT - \emptyset}$. $\endgroup$ – James Mar 25 '16 at 13:52
  • $\begingroup$ You probably mean $f(\emptyset)$. You tell me whether it's possible. By the way, the ratio could still be negative. $\endgroup$ – Yuval Filmus Mar 25 '16 at 13:53
  • $\begingroup$ Yes, thanks for the correction. By maximization with cardinality constraint $k$, I mean choosing a subset with cardinality less than or equal to $k$. Do you think the ratio can be negative? $\endgroup$ – James Mar 25 '16 at 21:16

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.