Abstract
The performances of two types of pure random walk (PRW) algorithms for a model of constraint satisfaction problems with growing domains (called Model RB) are investigated. Threshold phenomenons appear for both algorithms. In particular, when the constraint density r is smaller than a threshold value r d , PRW algorithms can solve instances of Model RB efficiently, but when r is bigger than the r d , they fail. Using a physical method, we find out the threshold values for both algorithms. When the number of variables N is large, the threshold values tend to zero, so generally speaking PRW does not work on Model RB.
Partially supported by NSFC 61370052 and 61370156.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Achlioptas, D., Kirousis, L., Kranakis, E., Krizanc, D., Molloy, M., Stamatiou, Y.: Random constraint satisfaction: a more accurate picture. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330, pp. 107–120. Springer, Heidelberg (1997)
Alekhnovich, M., Ben-Sasson, E.: Linear Upper Bounds for Random Walk on Small Density Random 3-cnfs. SIAM J. Comput. 36(5), 1248–1263 (2006)
Alphonse, É., Osmani, A.: A model to study phase transition and plateaus in relational learning. In: Železný, F., Lavrač, N. (eds.) ILP 2008. LNCS (LNAI), vol. 5194, pp. 6–23. Springer, Heidelberg (2008)
Broder, A.Z., Frieze, A.M., Upfal, E.: On the Satisfiability and Maximum Satisfiability of Random 3-CNF Formulas. In: Proc of SODA, pp. 322–330 (1993)
Chao, M., Franco, J.: Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem. SIAM J. Comput. 15(4), 1106–1118 (1986)
Cocco, S., Monasson, R., Montanari, A., Semerjian, G.: Analyzing search algorithms with physical methods. In: Percus, A., Istrate, G., Moore, C. (eds.) Computational Complexity and Statistical Physics, pp. 63–106. Oxford University Press (2006)
Coja-Oghlan, A., Frieze, A.: Analyzing Walksat on random formulas. In: Proc. of ANALCO, pp. 48–55 (2012)
Coja-Oghlan, A., Feige, U., Frieze, A., Krivelevich, M., Vilenchik, D.: On smoothed k-CNF formulas and the Walksat algorithm. In: Proc. of SODA, pp. 451–460 (2009)
Fan, Y., Shen, J.: On the phase transitions of random k-constraint satisfaction problems. Artif. Intell. 175, 914–927 (2011)
Fan, Y., Shen, J., Xu, K.: A general model and thresholds for random constraint satisfaction problems. Artif. Intell. 193, 1–17 (2012)
Gao, Y., Culberson, J.: Consistency and random constraint satisfaction problems. J. Artif. Intell. Res. 28, 517–557 (2007)
Gent, I., Macintype, E., Prosser, P., Smith, B., Walsh, T.: Random constraint satisfaction: flaws and structure. Constraints 6(4), 345–372 (2001)
Jiang, W., Liu, T., Ren, T., Xu, K.: Two hardness results on feedback vertex sets. In: Atallah, M., Li, X.-Y., Zhu, B. (eds.) FAW-AAIM 2011. LNCS, vol. 6681, pp. 233–243. Springer, Heidelberg (2011)
Lecoutre, C.: Constraint Networks: Techniques and Algorithms. John Wiley & Sons (2009)
Liu, T., Lin, X., Wang, C., Su, K., Xu, K.: Large Hinge Width on Sparse Random Hypergraphs. In: Proc of IJCAI, pp. 611–616 (2011)
Liu, T., Wang, C., Xu, K.: Large hypertree width for sparse random hypergraphs. J. Comb. Optim. (2014), doi 10.1007/s10878-013-9704-y
Mezard, M., Montanari, A.: Information, Physics and Computation. Oxford University Press (2009)
Richter, S., Helmert, M., Gretton, C.: A stochastic local search approach to vertex cover. In: Hertzberg, J., Beetz, M., Englert, R. (eds.) KI 2007. LNCS (LNAI), vol. 4667, pp. 412–426. Springer, Heidelberg (2007)
Rossi, F., Van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming. Elsevier (2006)
Smith, B.M., Dyer, M.E.: Locating the Phase Transition in Binary Constraint Satisfaction Problems. Artif. Intell. 81, 155–181 (1996)
Semerjian, G., Monasson, R.: Relaxation and Metastability in the Random Walk SAT search procedure. Phys. Rev. E 67, 066103 (2003)
Semerjian, G., Monasson, R.: A Study of Pure Random Walk on Random Satisfiability Problems with Physical Methods. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 120–134. Springer, Heidelberg (2004)
Schöning, U.: A probabilistic algorithm for k-SAT based on limited local search and restart. Algorithmica 32, 615–623 (2002)
Schöning, U.: A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: Proc. of FOCS, pp. 410–414 (1999)
Smith, B.: Constructing an asymptotic phase transition in random binary constraint satisfaction problems. Theoret. Comput. Sci. 265, 265–283 (2001)
Wang, C., Liu, T., Cui, P., Xu, K.: A note on treewidth in random graphs. In: Wang, W., Zhu, X., Du, D.-Z. (eds.) COCOA 2011. LNCS, vol. 6831, pp. 491–499. Springer, Heidelberg (2011)
Xu, K., Li, W.: Exact Phase Transitions in Random Constraint Satisfaction Problems. J. Artif. Intell. Res. 12, 93–103 (2000)
Xu, K., Li, W.: Many Hard Examples in Exact Phase Transitions. Theoret. Comput. Sci. 355, 291–302 (2006)
Xu, K., Boussemart, F., Hemery, F., Lecoutre, C.: Random Constraint Satisfaction: Easy Generation of Hard (Satisfiable) Instances. Artif. Intell. 171, 514–534 (2007)
Xu, W.: An analysis of backtrack-free algorithm on a constraint satisfaction problem with growing domains (in Chineses). Acta Mathematicae Applicatae Sinica (Chinese Series) (accepted, 2014)
Zhao, C., Zheng, Z.: Threshold behaviors of a random constraint satisfaction problem with exact phase transitions. Inform. Process. Lett. 111, 985–988 (2011)
Zhao, C., Zhang, P., Zheng, Z., Xu, K.: Analytical and Belief-propagation Studies of Random Constraint Satisfaction Problems with Growing Domains. Phys. Rev. E 85, 016106 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Xu, W., Gong, F. (2014). A Study of Pure Random Walk Algorithms on Constraint Satisfaction Problems with Growing Domains. In: Chen, J., Hopcroft, J.E., Wang, J. (eds) Frontiers in Algorithmics. FAW 2014. Lecture Notes in Computer Science, vol 8497. Springer, Cham. https://doi.org/10.1007/978-3-319-08016-1_25
Download citation
DOI: https://doi.org/10.1007/978-3-319-08016-1_25
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08015-4
Online ISBN: 978-3-319-08016-1
eBook Packages: Computer ScienceComputer Science (R0)