The Complexity of Valued Constraint Satisfaction Problems

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...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Κύριος συγγραφέας: Živný, Stanislav (Συγγραφέας)
Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
Γλώσσα:English
Έκδοση: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2012.
Σειρά:Cognitive Technologies,
Θέματα:
Διαθέσιμο Online:Full Text via HEAL-Link
Πίνακας περιεχομένων:
  • 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.