Problem of the month January 2011

The problem of this month is the following:

Given a skew-supermodular function [math]p:2^V\to \mathbb{Z}[/math] with a function evaluation oracle, is it possible to find a set [math]X\subseteq V[/math] in polynomial time such that [math]p(X)=\max\{p(Y): Y\subseteq V\}[/math]? The problem is open even if [math]p[/math] 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.