Classes of submodular constraints expressible by graph cuts

DOI10.1007/s10601-009-9078-zzbMath1208.68196OpenAlexW1974343882MaRDI QIDQ606899

Stanislav Živný, Peter G. Jeavons

Publication date: 19 November 2010

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10601-009-9078-z

zbMATH Keywords

min-cutminimisation of submodular functionspseudo-boolean optimisationsubmodular constraintsvalued constraint satisfaction problems

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (7)

Efficient minimization of higher order submodular functions using monotonic Boolean functions ⋮ Quadratic reformulations of nonlinear binary optimization problems ⋮ The expressive power of valued constraints: Hierarchies and collapses ⋮ The expressive power of binary submodular functions ⋮ Minimizing a sum of submodular functions ⋮ Generalized roof duality ⋮ A note on some collapse results of valued constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudo-Boolean optimization
• High-order consistency in valued constraint satisfaction
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• The expressive power of binary submodular functions
• 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
• Constraints, consistency and closure
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison
• On the supermodular knapsack problem
• Networks of constraints: Fundamental properties and applications to picture processing
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Supermodular functions and the complexity of MAX CSP
• The complexity of soft constraint satisfaction
• Level of repair analysis and minimum cost homomorphisms of graphs
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Maximizing Non-monotone Submodular Functions
• An Algebraic Characterisation of Complexity for Valued Constraint
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• A new approach to the maximum-flow problem
• 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: Classes of submodular constraints expressible by graph cuts