Problem of the month January 2011

The problem of this month is the following:

Given a skew-supermodular function $$p:2^V\to \mathbb{Z}$$ with a function evaluation oracle, is it possible to find a set $$X\subseteq V$$ in polynomial time such that $$p(X)=\max\{p(Y): Y\subseteq V\}$$ ? The problem is open even if $$p$$ is a crossing negamodular function.

It is well known that a supermodular function (given with a function-evaluation oracle) can be maximized in polynomial time. Simple considerations show that the same is true for an intersecting or a crossing supermodular function, too. In many applications we consider skew-supermodular functions, and in some abstract algorithms this open problem arises.