Hirsch, E. A., Worst-case time bounds for MAX-K-SAT w.r.t. the number of variables using local search.
Proceedings of RANDOM 2000, ICALP Workshops 2000, Proceedings in Informatics 8: 69-76. Carleton Scientific, 2000.

Abstract. During the past three years there was an explosion 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 in the input formula. Such 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 in the input formula. In this paper we give a randomized (1-\epsilon)-approximation algorithm for MAX-k-SAT. This algorithm runs in time of the order ck,\epsilonN, where N is the number of variables, and ck,\epsilon<2 is a constant depending on k and \epsilon.

Back to the list of papers