Abstract
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 Lovász 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. Wiley, Chichester (2000)
Fortnow’s, L.: complexity blog, http://blog.computationalcomplexity.org/2009/06/kolmogorov-complexity-proof-of-lov.html
Moser, R.A.: A constructive proof of Lovász local lemma. In: Proceedings 41st Ann. ACM Symposium on Theory of Computing, pp. 343–350 (2009)
Moser, R.A., Tárdos, G.: A constructive proof of the general Lovász Local Lemma, http://arxiv.org/abs/0903.0544
Schöning, U.: A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: Proceedings 40th Annual Symposium on Foundations of Computer Science, pp. 410–414 (1999)
Schöning, U.: A probabilistic algorithm for k-SAT based on limited local search and restart. Algorithmica 32(4), 615–623 (2002)
Schöning, U.: Principles of stochastic local search. In: Akl, S.G., Calude, C.S., Dinneen, M.J., Rozenberg, G., Wareham, H.T. (eds.) UC 2007. LNCS, vol. 4618, pp. 178–187. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schöning, U. (2010). Comparing Two Stochastic Local Search Algorithms for Constraint Satisfaction Problems. In: Ablayev, F., Mayr, E.W. (eds) Computer Science – Theory and Applications. CSR 2010. Lecture Notes in Computer Science, vol 6072. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13182-0_34
Download citation
DOI: https://doi.org/10.1007/978-3-642-13182-0_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13181-3
Online ISBN: 978-3-642-13182-0
eBook Packages: Computer ScienceComputer Science (R0)