Annals of Pure and Applied Logic 113(1-3), pp. 81-94, 2001.

**Abstract.**
We describe approximation algorithms for (unweighted) MAX SAT with
performance ratios arbitrarily close to 1,
in particular, when performance
ratios exceed the limits of polynomial-time approximation.
Namely, given a polynomial-time *a*-approximation
algorithm *A*_{0},
we construct an (*a*+*e*)-approximation algorithm *A*.
The algorithm *A* runs in time of the order
*c ^{ek}*,
where

[ Full text is available on request ]

Back to the list of papers