Hirsch, E. A., Worst-case study of local search for MAX-k-SAT.
Discrete Applied Mathematics 130/2: 173-184, 2003.

Abstract. During the past three years there was a considerable growth in the number of algorithms solving MAX-SAT and MAX-2-SAT in worst-case time of the order cK, where c<2 is a constant, and K is the number of clauses of the input formula. However, similar bounds w.r.t. the number of variables instead of the number of clauses are not known.

Also, it was proved that approximate solutions for these problems (even beyond inapproximability ratios) can be obtained faster than exact solutions. However, the corresponding exponents still depended on the number of clauses of the input formula. In this paper, we give a randomized (1-\epsilon)-approximation algorithm for MAX-k-SAT whose worst-case time bound depends on the number of variables.

Our algorithm and its analysis are based on Schöning's proof of the best current worst-case time bound for k-SAT [Sch99]. Similarly to Schöning's algorithm (which is also very close to Papadimitriou's algorithm [Pap91] and the experimentally successful WalkSAT family by Selman et al. [SKC94,MSK97], our algorithm makes random walks of polynomial length. We prove that the probability of error in each walk is at most 1-ck,\epsilon-N, where N is the number of variables, and ck,\epsilon<2 is a constant depending on k and \epsilon. Therefore, making \lceil-ln\rho\rceil * ck,\epsilonN such walks gives the probability of error bounded from above by any predefined constant \rho>0.

Full text (draft): [ .ps.gz (25 Kb) ]

Back to the list of papers