Minimization of locally defined submodular functions by optimal soft arc consistency
From MaRDI portal
Publication:1020491
DOI10.1007/s10601-007-9037-5zbMath1180.90262OpenAlexW2005103485MaRDI QIDQ1020491
Publication date: 29 May 2009
Published in: Constraints (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10601-007-9037-5
linear programmingdiscrete optimizationsoft constraintsmajority operationvalued constraint satisfaction problem
Related Items (7)
The Expressive Power of Binary Submodular Functions ⋮ Classes of submodular constraints expressible by graph cuts ⋮ Efficient minimization of higher order submodular functions using monotonic Boolean functions ⋮ The expressive power of binary submodular functions ⋮ Soft arc consistency revisited ⋮ Minimizing a sum of submodular functions ⋮ The Power of Linear Programming for General-Valued CSPs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pseudo-Boolean optimization
- Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
- Arc consistency for soft constraints
- Solving weighted CSP by maintaining arc consistency
- High-order consistency in valued constraint satisfaction
- Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
- A dichotomy theorem for maximum generalized satisfiability problems.
- Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
- On submodular function minimization
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- The partial constraint satisfaction problem: Facets and lifting theorems
- Submodular functions and electrical networks
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- Realization of set functions as cut functions of graphs and hypergraphs
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A fully combinatorial algorithm for submodular function minimization.
- Reduction operations in fuzzy or valued constraint satisfaction
- Supermodular functions and the complexity of MAX CSP
- The complexity of soft constraint satisfaction
- Combinatorial problems raised from 2-semilattices
- Submodular functions and optimization.
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- An Algebraic Characterisation of Complexity for Valued Constraint
- Generalized Arc Consistency for Positive Table Constraints
- Minimum cuts, modular functions, and matroid polyhedra
- A new approach to the maximum-flow problem
- Finding the nearest point in A polytope
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- A Faster Scaling Algorithm for Minimizing Submodular Functions
- Classifying the Complexity of Constraints Using Finite Algebras
- A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
- The Approximability of Three-valued MAX CSP
- Principles and Practice of Constraint Programming – CP 2004
- Tractable constraints on ordered domains
This page was built for publication: Minimization of locally defined submodular functions by optimal soft arc consistency
