# Maximizing a skew-supermodular function

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 was shown by Toshimasa Ishii and Kazuhisa Makino ^{[1]} that the problem is hard even for negamodular functions. More precisely, they showed that any algorithm for the posimodular function minimization problem requires [math]\Omega(2^{\frac{n}{7.54}})[/math] oracle calls. Furthermore, if the range of the set function is [math]\{0,1\dots,d\}[/math], then [math]\Omega(2^{\frac{d}{15.08}})[/math] oracle calls are necessary.

## Remarks

There are several polynomial-time combinatorial algorithms for minimizing a submodular function (which is equivalent to maximizing a supermodular function); see ^{[2]} ^{[3]} for surveys.

## References

- ↑ T. Ishii, K. Makino,
*Posimodular Function Optimization*, arXiv link - ↑ S.T. McCormick,
*Submodular function minimization*, DOI link, author link - ↑ S. Iwata,
*Submodular function minimization*, DOI link, pdf link