The expressive power of binary submodular functions
From MaRDI portal
Publication:967393
DOI10.1016/j.dam.2009.07.001zbMath1229.90093OpenAlexW2964332764MaRDI QIDQ967393
Stanislav Živný, Peter G. Jeavons, David A. Cohen
Publication date: 28 April 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2009.07.001
min-cutdecomposition of submodular functionspseudo-Boolean optimisationsubmodular function minimisation
Related Items (14)
Core-based criterion for extreme supermodular functions ⋮ On a general framework for network representability in discrete optimization ⋮ Classes of submodular constraints expressible by graph cuts ⋮ Hypergraph Cuts with General Splitting Functions ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ The Complexity of Valued CSPs ⋮ Efficient minimization of higher order submodular functions using monotonic Boolean functions ⋮ Quadratic reformulations of nonlinear binary optimization problems ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms ⋮ Minimizing a sum of submodular functions ⋮ Generalized roof duality ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ On a General Framework for Network Representability in Discrete Optimization ⋮ The Power of Linear Programming for General-Valued CSPs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Classes of submodular constraints expressible by graph cuts
- Pseudo-Boolean optimization
- Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
- Submodular function minimization
- 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
- Recognition problems for special classes of polynomials in 0-1 variables
- The ellipsoid method and its consequences in combinatorial optimization
- Geometric algorithms and combinatorial optimization
- Constraints, consistency and closure
- Submodular functions and electrical networks
- Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison
- On the supermodular knapsack problem
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A fully combinatorial algorithm for submodular function minimization.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Perspectives of Monge properties in optimization
- Supermodular functions and the complexity of MAX CSP
- The complexity of soft constraint satisfaction
- Level of repair analysis and minimum cost homomorphisms of graphs
- Supermodular functions on finite lattices
- Submodular functions and optimization.
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- Maximizing Non-monotone Submodular Functions
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- The approximability of MAX CSP with fixed-value constraints
- An Algebraic Characterisation of Complexity for Valued Constraint
- Graphical Models, Exponential Families, and Variational Inference
- Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
- An analysis of approximations for maximizing submodular set functions—I
- A Faster Scaling Algorithm for Minimizing Submodular Functions
- Classifying the Complexity of Constraints Using Finite Algebras
- Some Network Flow Problems Solved with Pseudo-Boolean Programming
- The Approximability of Three-valued MAX CSP
- A Selection Problem of Shared Fixed Costs and Network Flows
This page was built for publication: The expressive power of binary submodular functions
