Efficient Minimization of Higher Order Submodular Functions using Monotonic Boolean Functions

Understand

Submodular function minimization is a key problem in a wide variety of applications in machine learning, economics, game theory, computer vision, and many others.

• The general solver has a complexity of $O(n^3 \log^2 n .
• E +n^4 {\log}^{O(1)} n)$ where $E$ is the time required to evaluate the function and $n$ is the number of variables \cite{Lee2015}.
• On the other hand, many computer vision and machine learning problems are defined over special subclasses of submodular functions that can be written as the sum of many submodular cost functions defined over cliques containing few variables.