The expressive power of valued constraints: Hierarchies and collapses

DOI10.1016/j.tcs.2008.08.036zbMath1157.68061OpenAlexW2115373747MaRDI QIDQ959827

Stanislav Živný, David A. Cohen, Peter G. Jeavons

Publication date: 12 December 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://ora.ox.ac.uk/objects/uuid:d0ad4ee4-b42e-4144-a8e3-c6de99a7d677

zbMATH Keywords

expressibilitypolymorphismsvalued constraint satisfactionfeasibility polymorphismsfractional polymorphismsmax-closed cost functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (2)

Binarisation for Valued Constraint Satisfaction Problems ⋮ A note on some collapse results of valued constraints

Cites Work

• Classes of submodular constraints expressible by graph cuts
• Pseudo-Boolean optimization
• Submodular function minimization
• A faster strongly polynomial time algorithm for submodular function minimization
• Bases for Boolean co-clones
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• Tree clustering for constraint networks
• Constraints, consistency and closure
• On the algebraic structure of combinatorial problems
• Minimizing symmetric submodular functions
• How to determine the expressive power of constraints
• Submodular functions and electrical networks
• Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison
• Networks of constraints: Fundamental properties and applications to picture processing
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• The complexity of soft constraint satisfaction
• Submodular functions and optimization.
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Closure properties of constraints
• A Faster Scaling Algorithm for Minimizing Submodular Functions
• Classifying the Complexity of Constraints Using Finite Algebras
• Tractable constraints on ordered domains
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The expressive power of valued constraints: Hierarchies and collapses