Problem of the month February 2011

The problem is not prolenged any more, though we have't solved it yet. Some partial results are given on the discussion page of the problem.

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.