The Complexity of Valued Constraint Satisfaction Problems

• Main Author: Živný, Stanislav (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2012.
• Series: Cognitive Technologies,
• Subjects: Computer science.; Computers.; Computer science > Mathematics.; Artificial intelligence.; Mathematical logic.; Computer Science.; Theory of Computation.; Artificial Intelligence (incl. Robotics).; Mathematical Logic and Foundations.; Mathematics of Computing.

The topic of this book is the following optimisation problem: given a set of discrete variables and a set of functions, each depending on a subset of the variables, minimise the sum of the functions over all variables. This fundamental research problem has been studied within several different conte...

Table of Contents:

• Chap. 1 Introduction
• Chap. 2 Background
• Chap. 3 Expressibility of Valued Constraints
• Chap. 4 Expressibility of Fixed-Arity Languages
• Chap. 5 Expressibility of Submodular Languages
• Chap. 6 Non-expressibility of Submodular Languages
• Chap. 7 Tractable Languages
• Chap. 8  Conservative Languages
• Chap. 9 The Power of Linear Programming
• Chap. 10 Hybrid Tractability
• Chap. 11 Summary and Open Problems
• References
• Index.