I have been doing a small review of the literature on submodular optimization.

Something seemed strange to me: although there is a greedy algorithm that provides limited optimization for a monotonous submodular function, I could not find much of what has been said about maximizing a non-monotonous submodular function, or at least one that is not required. To be not negative.

Some definitions: let $ S $ Be a finite set.

$ f: 2 ^ S rightarrow mathbb {R} $ is **submodular** yes for every $ U, V subseteq S $,

$$

f (U cup V) + f (U cap V) leq f (U) + f (V)

$$

$ f $ is **monotonous** Yes always $ U subseteq V $, $ f (U) leq f (V) $.

$ f $ is **not negative** Yes $ F (U) geq 0 $ for all $ U subseteq S $.

What is my motivation? If they give us a graph, $ mathcal {G} = ( mathcal {E}, mathcal {V}) $, with *possibly negative* edge weights $ w: mathcal {E} rightarrow mathbb {R} $clearly states that

$$ f: 2 ^ mathcal {E} rightarrow mathbb {R} $$

given by

$$ U mapsto sum_ {i j en U} w ^ {i j} $$

it's submodular (in fact **modular** Since inclusion-exclusion remains in the nose!) Regardless of whether the weights are positive or negative.

Is there a greedy algorithm to maximize such functions?

It is so, I would appreciate an explanation or a reference below.