The complexity of valued constraint satisfaction

MaRDI QIDQ4967163zbMATH OpenFDO

Authors Andrei Krokhin, S. Zivny, P. Jeavons

Publication date 3 July 2019

Full work available at URL http://bulletin.eatcs.org/index.php/beatcs/article/view/266/249

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of valued CSPs
• Complexity of the counting constraint satisfaction problem
• The complexity of valued constraint satisfaction problems
• An Algebraic Approach to Valued Constraint Satisfaction
• The complexity of general-valued CSPs

Cited in

(21)

• Enhanced multiple-point statistical simulation with backtracking, forward checking and conflict-directed backjumping
• Finding a given number of solutions to a system of fuzzy constraints
• A Galois connection for valued constraint languages of infinite size
• Algebraic properties of valued constraint satisfaction problem
• Sherali-Adams relaxations for valued CSPs
• Necessary conditions for tractability of valued CSPs
• The Expressive Power of Valued Constraints: Hierarchies and Collapses
• The complexity of valued constraint satisfaction problems
• Hybrid tractable classes of constraint problems
• Backdoor sets for CSP
• The complexity of valued CSPs
• The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
• An Algebraic Approach to Valued Constraint Satisfaction
• Hybrid VCSPs with crisp and valued conservative templates
• The power of linear programming for general-valued CSPs
• Bounded backtracking for the valued constraint satisfaction problems
• Principles and Practice of Constraint Programming – CP 2004
• PTAS for Sparse General-valued CSPs
• Hybrid tractability of valued constraint problems
• Valued constraint satisfaction problems
• The expressive power of valued constraints: Hierarchies and collapses

This page was built for publication: The complexity of valued constraint satisfaction

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