Analyzing Walksat on random formulas

Preprint English OPEN
Coja-Oghlan, Amin ; Frieze, Alan (2011)
  • Related identifiers: doi: 10.1137/12090191X
  • Subject: Mathematics - Combinatorics | Computer Science - Discrete Mathematics | 68R01

Let F be a uniformly distributed random k-SAT formula with n variables and m clauses. We prove that the Walksat algorithm from Papadimitriou (FOCS 1991)/Schoning (FOCS 1999) finds a satisfying assignment of F in polynomial time w.h.p. if m/n<\rho 2^k/k for a certain constant \rho>0. This is an improvement by a factor of $\Theta(k)$ over the best previous analysis of Walksat from Coja-Oghlan, Feige, Frieze, Krivelevich, Vilenchik (SODA 2009).
  • References (18)
    18 references, page 1 of 2

    [2] D. Achlioptas, C. Moore: Random k-SAT: two moments suffice to cross a sharp threshold. SIAM Journal on Computing 36 (2006) 740-762.

    [3] D. Achlioptas, Y. Peres: The threshold for random k-SAT is 2k ln 2 − O(k). Journal of the AMS 17 (2004) 947-973.

    [4] M. Alekhnovich and E. Ben-Sasson: Linear upper bounds for random walk on small density random 3-CNFs. SIAM J. Comput. 36 (2007) 1248-1263.

    [5] A. Broder, A. Frieze, E. Upfal: On the satisfiability and maximum satisfiability of random 3-CNF formulas. Proc. 4th SODA (1993) 322-330.

    [6] M.-T. Chao, J. Franco: Probabilistic analysis of a generalization of the unit-clause literal selection heuristic for the k-satisfiability problem. Inform. Sci. 51 (1990) 289-314.

    [7] V. Chva´tal, B. Reed: Mick gets some (the odds are on his side). Proc. 33th FOCS (1992) 620-627.

    [8] A. Coja-Oghlan: A better algorithm for random k-SAT. SIAM J. Computing 39 (2010) 2823-2864.

    [9] A. Coja-Oghlan, U. Feige, A. Frieze, M. Krivelevich, D. Vilenchik: On smoothed k-CNF formulas and the Walksat algorithm. Proc. 20th SODA (2009) 451-460.

    [10] A. Frieze, S. Suen: Analysis of two simple heuristics on a random instance of k-SAT. Journal of Algorithms 20 (1996) 312-355.

    [11] M. Hajiaghayi, G. Sorkin: The satisfiability threshold of random 3-SAT is at least 3.52. IBM Research Report RC22942 (2003).

  • Metrics
    No metrics available
Share - Bookmark