Classes of submodular constraints expressible by graph cuts
From MaRDI portal
Publication:606899
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
min-cutminimisation of submodular functionspseudo-boolean optimisationsubmodular constraintsvalued constraint satisfaction problems
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
