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
c^{K}, 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-c_{k,\epsilon}^{-N},
where N is the number of variables,
and c_{k,\epsilon}<2 is a constant depending on k and \epsilon.
Therefore, making
\lceil-ln\rho\rceil * c_{k,\epsilon}^{N} 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