nach oben

2012 | Buch

Kapitel lesen Erstes Kapitel lesen

The Complexity of Valued Constraint Satisfaction Problems

verfasst von: Stanislav Živný

Verlag: Springer Berlin Heidelberg

Buchreihe : Cognitive Technologies

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

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 contexts of discrete mathematics, computer science and artificial intelligence under different names: Min-Sum problems, MAP inference in Markov random fields (MRFs) and conditional random fields (CRFs), Gibbs energy minimisation, valued constraint satisfaction problems (VCSPs), and, for two-state variables, pseudo-Boolean optimisation.

In this book the author presents general techniques for analysing the structure of such functions and the computational complexity of the minimisation problem, and he gives a comprehensive list of tractable cases. Moreover, he demonstrates that the so-called algebraic approach to VCSPs can be used not only for the search for tractable VCSPs, but also for other questions such as finding the boundaries to the applicability of certain algorithmic techniques.

The book is suitable for researchers interested in methods and results from the area of constraint programming and discrete optimisation.

Inhaltsverzeichnis

Frontmatter

Part I

Chapter 1. Background

Abstract

Chapter 1 introduces the necessary background. It defines valued constraint satisfaction problems and gives examples of problems that can be formulated as such. Secondly, it defines the key concept of expressibility and introduces certain algebraic properties that play a key role in the complexity analysis of valued constraint satisfaction problems. Finally, it presents the notion of submodularity and surveys known results regarding optimising submodular functions.

Stanislav Živný

Expressive Power

Frontmatter

Chapter 2. Expressibility of Valued Constraints

Abstract

Chapter 2 presents the indicator problem, a universal construction for determining the expressibility of crisp constraints. Secondly, it contains a generalisation of the indicator problem to valued constraints. Finally, it presents the recently developed algebraic theory for studying the complexity of valued constraints in terms of the associated fractional polymorphisms.

Stanislav Živný

Chapter 3. Expressibility of Fixed-Arity Languages

Abstract

Chapter 3 studies the expressive power of various classes of valued constraints. It contains several results of the following form: let \(\mathcal{C}\) be a class of valued constraints with functions of unbounded arities; then \(\mathcal{C}\) can be expressed by a subset of \(\mathcal{C}\) consisting of valued constraints with functions of a fixed bounded arity. The only known class for which this is not true is the class of finite-valued max-closed functions of different arities. This chapter also presents some results on the algebraic properties of finite-valued max-closed functions.

Stanislav Živný

Chapter 4. Expressibility of Submodular Languages

Abstract

Chapter 4 focuses on the expressive power of binary submodular functions. Known and new classes of submodular functions that are expressible by binary submodular functions are presented. There is a close relationship between the expressive power of binary submodular functions and solving submodular valued constraint satisfaction problems via the minimum cut problem: showing that a class \(\mathcal{C}\) of submodular functions is expressible by binary submodular functions is equivalent to showing that functions from \(\mathcal{C}\) can be minimised efficiently via the minimum cut problem.

Stanislav Živný

Chapter 5. Non-expressibility of Submodular Languages

Abstract

Chapter 5 studies the problem of whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using the connection between the expressive power of submodular functions and certain algebraic properties of functions described in earlier chapters, a negative answer to this question is shown. Consequently, there are submodular functions that cannot be reduced to the minimum cut problem via the expressibility reduction.

Stanislav Živný

Tractability

Frontmatter

Chapter 6. Tractable Languages

Abstract

Chapter 6 surveys a list of known tractable valued constraint languages. Quite strikingly, all of them can be characterised by simple fractional polymorphisms.

Stanislav Živný

Chapter 7. Conservative Languages

Abstract

Chapter 7 presents recent results on the complexity of conservative valued constraint languages. These are languages including all unary functions. The tractable conservative languages, which strictly include submodular functions, are precisely characterised by two complementary fractional polymorphisms.

Stanislav Živný

Chapter 8. The Power of Linear Programming

Abstract

Chapter 8 shows recent results on the power of linear programming for valued constraint satisfaction problems. In particular, it presents an algebraic characterisation, in terms of fractional polymorphisms, of valued constraint languages that are tractable via a standard linear programming relaxation. This result has several algorithmic consequences such as establishing the tractability of submodular functions on trees.

Stanislav Živný

Chapter 9. Hybrid Tractability

Abstract

Chapter 9 is devoted to recent results on hybrid tractability of valued constraint satisfaction problems, that is, reasons for tractability that do not follow from the restriction on the functions, such as submodularity, or on the structure of the instance, such as bounded treewidth.

Stanislav Živný

Chapter 10. Summary and Open Problems

Abstract

Chapter 10 summarises the content of the book and list some open problems.

Stanislav Živný

Backmatter

Titel: The Complexity of Valued Constraint Satisfaction Problems
verfasst von: Stanislav Živný
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-33974-5
Print ISBN: 978-3-642-33973-8
DOI: https://doi.org/10.1007/978-3-642-33974-5