An Algebraic Characterisation of Complexity for Valued Constraint

DOI10.1007/11889205_10MaRDI QIDQ3524237zbMATH OpenOpenAlexFDO

Authors M. C. Cooper, David A. Cohen, P. Jeavons

Publication date 9 September 2008

Published in Principles and Practice of Constraint Programming - CP 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11889205_10

Mathematics Subject Classification ID

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

Recommendations

• An algebraic theory of complexity for valued constraints: establishing a Galois connection
• An algebraic theory of complexity for discrete optimization.
• The complexity of general-valued CSPs
• The complexity of soft constraint satisfaction
• Soft constraints: complexity and multimorphisms

Cited in

(21)

• Minimization of locally defined submodular functions by optimal soft arc consistency
• The complexity of soft constraint satisfaction
• An algebraic theory of complexity for valued constraints: establishing a Galois connection
• The Expressive Power of Binary Submodular Functions
• The Expressive Power of Valued Constraints: Hierarchies and Collapses
• Soft Constraints Processing over Divisible Residuated Lattices
• An Algebraic Approach to Valued Constraint Satisfaction
• The power of linear programming for general-valued CSPs
• The complexity of general-valued CSPs
• An algebraic theory of complexity for discrete optimization.
• Introduction to the Maximum Solution Problem
• The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
• Soft constraints: complexity and multimorphisms
• Classes of submodular constraints expressible by graph cuts
• The complexity of resilience problems via valued constraint satisfaction problems
• The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
• Temporal valued constraint satisfaction problems
• The complexity of resilience problems via valued constraint satisfaction
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• The expressive power of binary submodular functions
• A note on some collapse results of valued constraints

This page was built for publication: An Algebraic Characterisation of Complexity for Valued Constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3524237)