Maximizing a skew-supermodular function

From Egres Open
Jump to: navigation, search

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.

Solved b.jpg

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.


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.


  1. T. Ishii, K. Makino, Posimodular Function Optimization, arXiv link
  2. S.T. McCormick, Submodular function minimization, DOI link, author link
  3. S. Iwata, Submodular function minimization, DOI link, pdf link