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

Back to the list of papers