Talk:Maximizing a skew-supermodular function

-- Athos 17:10, 10 March 2011 (UTC)

I write some partial results here without a proof: if one is interested in proofs, contact me (Attila Bernath, athos at cs dot elte dot hu).

We tried to solve the special case of maximizing a negamodular function (or equivalently, minimizing a posimodular function) i.e. find $$\min\{f(X): X\subseteq V, X\ne \emptyset\}$$ where f is posimodular.

We tried an approach similar to Nagamochi's Minimum Degree Ordering which solves the special case, when f is symmetric an submodular.

Let us call a nonempty subset X extreme, if $$f(Y)\gtf(X)$$ for every proper nonempty subset Y of X. Note that an inclusionwise minimal subset is also extreme.

It is easy to check that extreme subsets form a laminar family. The approach of Nagamochi is the following: find a pair of nodes that is only separated by singleton extreme subsets (such a pair exists even for posimodular functions, since extreme subsets form a laminar family: note however that this is no longer true for skew-submodular functions, since there can be many extreme subsets in that case, take for example $$f(X)=-|X|$$ ; every nonempty subset is extreme). Nagamochi shows that the last two elements of a simply defined ordering forms such a pair. This result gives a simple algorithm to find all extreme subsets.

Nagamochi in fact shows that the last two elements of his ordering is even more special: it is flat pair defined as follows: a pair of nodes u,v is a flat pair, if for any X separating u and v there exists an $$x\in X$$ such that $$f(x)\le f(X)$$ .

We have proved that a flat pair also exists for posimodular functions. But how to find one?