Comparing Two Stochastic Local Search Algorithms for Constraint Satisfaction Problems (Invited Talk)

摘要

In this survey we compare the similarities, differences and the complexities of two very different approaches to solve a general constraint satisfaction probblems (CSP). One is the algorithm used in Moser's ingenious proof of a constructive version of Lovasz Local Lemma [3], the other is the k-SAT random walk algorithm from [5,6], generalized to CSP's. There are several similarities, both algorithms use a version of stochastic local search (SLS), but the kind of local search neighborhood is defined differently, also the preconditions for the algorithms to work (efficiently) are quite different. constraint satisfaction problem, CSP, Lovasz Local Lemma, SAT, satisfiability algorithm, stochastic local search, SLS.