Efficient minimization of higher order submodular functions using monotonic Boolean functions

DOI10.1016/J.DAM.2016.11.022zbMATH Open1422.68136arXiv1109.2304OpenAlexW2964255216MaRDI QIDQ507571FDOQ507571

Chris Russell, Srikumar Ramalingam, L'ubor Ladický, Philip H. S. Torr

Publication date: 6 February 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: 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}lo{g}^{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. In such functions, the pseudo-Boolean (or polynomial) representation cite{BorosH02} of these subclasses are of degree (or order, or clique size) $k$ where $klln$. In this work, we develop efficient algorithms for the minimization of this useful subclass of submodular functions. To do this, we define novel mapping that transform submodular functions of order $k$ into quadratic ones. The underlying idea is to use auxiliary variables to model the higher order terms and the transformation is found using a carefully constructed linear program. In particular, we model the auxiliary variables as monotonic Boolean functions, allowing us to obtain a compact transformation using as few auxiliary variables as possible.

Full work available at URL: https://arxiv.org/abs/1109.2304

Recommendations

• Subquadratic submodular function minimization
• A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract)
• Minimizing a sum of submodular functions
• The Expressive Power of Binary Submodular Functions
• Learning with submodular functions: a convex optimization perspective

zbMATH Keywords

submodular functionsDedekind numbermax-flow/mincut algorithmmonotonic Boolean functionsquadratic pseudo-Boolean functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30)

Cites Work

• The Concave-Convex Procedure
• The ellipsoid method and its consequences in combinatorial optimization
• Quadratization of symmetric pseudo-Boolean functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Gadgets, Approximation, and Linear Programming
• Pseudo-Boolean optimization
• Title not available (Why is that?)
• An Algebraic Theory of Complexity for Discrete Optimization
• On Dedekind's Problem: The Number of Monotone Boolean Functions
• Title not available (Why is that?)
• A faster strongly polynomial time algorithm for submodular function minimization
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Supermodular functions on finite lattices
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• An analysis of approximations for maximizing submodular set functions—I
• The expressive power of binary submodular functions
• Title not available (Why is that?)
• On submodular function minimization
• A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• A Selection Problem of Shared Fixed Costs and Network Flows
• Title not available (Why is that?)
• Minimizing a sum of submodular functions
• Minimization of locally defined submodular functions by optimal soft arc consistency
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• On the supermodular knapsack problem
• A fully combinatorial algorithm for submodular function minimization.
• Title not available (Why is that?)
• Classes of submodular constraints expressible by graph cuts

Cited In (3)

• Quadratic reformulations of nonlinear binary optimization problems
• On a general framework for network representability in discrete optimization
• Graph cuts with interacting edge weights: examples, approximations, and algorithms

Uses Software

• JBool

This page was built for publication: Efficient minimization of higher order submodular functions using monotonic Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507571)