Efficient Minimization of Higher Order Submodular Functions using Monotonic Boolean Functions

Details Efficient Minimization of Higher Order Submodular Functions using Monotonic Boolean Functions Efficient Minimization of Higher Order Submodular Functions using Monotonic Boolean Functions

2011-09-11

arxiv.org/abs/1109.2304v1

Computer Science

Data Structures and Algorithms

Scientific paper

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^6+n^5L)$ where $L$ is the time required to evaluate the function and $n$ is the number of variables \cite{orlin09}. On the other hand, many useful applications in computer vision and machine learning applications are defined over a special subclasses of submodular functions in which that can be written as the sum of many submodular cost functions defined over cliques containing few variables. In such functions, the pseudo-Boolean (or polynomial) representation \cite{BorosH02} of these subclasses are of degree (or order, or clique size) $k$ where $k<

Affiliated with

Also associated with

No associations

Rating

Efficient Minimization of Higher Order Submodular Functions using Monotonic Boolean Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Minimization of Higher Order Submodular Functions using Monotonic Boolean Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Minimization of Higher Order Submodular Functions using Monotonic Boolean Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-20062