Efficient minimization of higher order submodular functions using monotonic Boolean functions

DOI10.1016/J.DAM.2016.11.022MaRDI QIDQ507571zbMATHOpenAlexFDO

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

Publication date 6 February 2017

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

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

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)

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.

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

Cites work

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

Cited in

(6)

• Quadratic decomposable submodular function minimization: theory and practice
• On a general framework for network representability in discrete optimization
• The expressive power of binary submodular functions
• Graph cuts with interacting edge weights: examples, approximations, and algorithms
• The Expressive Power of Binary Submodular Functions
• Quadratic reformulations of nonlinear binary optimization problems

Describes a project that uses

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)