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
