Efficient minimization of higher order submodular functions using monotonic Boolean functions
From MaRDI portal
Publication:507571
DOI10.1016/j.dam.2016.11.022zbMath1422.68136arXiv1109.2304OpenAlexW2964255216MaRDI QIDQ507571
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)
Full work available at URL: https://arxiv.org/abs/1109.2304
submodular functionsDedekind numbermax-flow/mincut algorithmmonotonic Boolean functionsquadratic pseudo-Boolean functions
Related Items
On a general framework for network representability in discrete optimization ⋮ Quadratic reformulations of nonlinear binary optimization problems ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms
Uses Software
Cites Work
- Quadratization of symmetric pseudo-Boolean functions
- Classes of submodular constraints expressible by graph cuts
- Pseudo-Boolean optimization
- Minimizing a sum of submodular functions
- A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
- The expressive power of binary submodular functions
- A faster strongly polynomial time algorithm for submodular function minimization
- Minimization of locally defined submodular functions by optimal soft arc consistency
- Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
- On submodular function minimization
- The ellipsoid method and its consequences in combinatorial optimization
- A push-relabel framework for submodular function minimization and applications to parametric optimization
- On the supermodular knapsack problem
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A fully combinatorial algorithm for submodular function minimization.
- 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 Concave-Convex Procedure
- Gadgets, Approximation, and Linear Programming
- Some Network Flow Problems Solved with Pseudo-Boolean Programming
- An Algebraic Theory of Complexity for Discrete Optimization
- On Dedekind's Problem: The Number of Monotone Boolean Functions
- A Selection Problem of Shared Fixed Costs and Network Flows
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
