Erschienen: 26.03.2013 Abbildung von Moser | Exact Algorithms for Constraint Satisfaction Problems | 2013


Exact Algorithms for Constraint Satisfaction Problems

lieferbar, ca. 10 Tage

2013. Buch. 215 S. Softcover

Logos. ISBN 978-3-8325-3369-4

Format (B x L): 14,5 x 21 cm

In englischer Sprache


The Boolean satisfiability problem (SAT) and its generalization to variables of higher arities ? constraint satisfaction problems (CSP) ? can arguably be called the most ``natural'' of all NP-complete problems. The present work is concerned with their algorithmic treatment. It consists of two parts.

The first part investigates CSPs for which satisfiability follows from the famous Lovász Local Lemma. Since its discovery in 1975 by Paul Erd H{os and László Lovász, it has been known that CSPs without dense spots of interdependent constraints always admit a satisfying assignment. However, an iterative procedure to discover such an assignment was not available. We refine earlier attempts at making the Local Lemma algorithmic and present a polynomial time algorithm which is able to make almost all known applications constructive.

In the second part, we leave behind the class of polynomial time tractable problems and instead investigate the randomized exponential time algorithm devised and analyzed by Uwe Schöning in 1999, which solves arbitrary clause satisfaction problems. Besides some new interesting perspectives on the algorithm, the main contribution of this part consists of a refinement of earlier approaches at derandomizing Schöning's algorithm. We present a deterministic variant which losslessly reaches the performance of the randomized original.


  • Dieses Set enthält folgende Produkte:
      Auch in folgendem Set erhältlich:
      • nach oben

        Ihre Daten werden geladen ...