Some Heuristic Analysis of Local Search Algorithms for SAT Problems

  • Osamu Watanabe
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3777)


By using heuristic analysis proposed in [WSA03], we investigate the dynamical behavior of greedy local search algorithms for satisfiability (SAT) problems. We observe that the difference between hard and easy instances is relatively small while there are enough places to be improved locally, and that the difference becomes crucial when all such places are processed. We also show that a tabu search type restriction could be useful for improving the efficiency of greedy local search algorithms.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [Ach01]
    Achlioptas, D.: Lower bounds for random 3-SAT via differential equations. Theoret. Comput. Sci. 265, 159–185 (2001)zbMATHCrossRefMathSciNetGoogle Scholar
  2. [Betal03]
    Barthel, W., Hartmann, A., Weigt, M.: Solving satisfiability by fluctuations: The dynamics of stochastic local search algorithms. Physical Review E 67(066104) (2003)Google Scholar
  3. [SAT00]
    Special Issue “SAT-2000”. J. of Automated Reasoning 24(1-2) (2000)Google Scholar
  4. [SM03]
    Semerjian, G., Monasson, R.: Relaxation and metastability in a local search procedure for the random satisfiability problem. Physical Review E 67(066103) (2003)Google Scholar
  5. [SS96]
    Sipser, M., Spielman, D.: Expander codes. IEEE Trans. on Information Theory 42(6), 1710–1719 (1996)zbMATHCrossRefMathSciNetGoogle Scholar
  6. [WSA03]
    Watanabe, O., Sawai, T., Takahashi, H.: Analysis of a randomized local search algorithm for LDPCC decoding problem. In: Albrecht, A.A., Steinhöfel, K. (eds.) SAGA 2003. LNCS, vol. 2827, pp. 50–60. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  7. [Wat05]
    Watanabe, O.: Pseudo expectation: A tool for analyzing local search algorithms, Progress of Theoret. Physics Supplement 157, 338–344 (2005) (A detail version is available: Research Report C-198, Dept. of Mathematical and Comput. Sci., Tokyo Inst. of Tech.)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Osamu Watanabe
    • 1
  1. 1.Department of Mathematical and Computing ScienceTokyo Institute of TechnologyTokyoJapan

Personalised recommendations