E.Dantsin, M.Gavrilovich, E.A.Hirsch, B.Konev, MAX SAT approximation beyond the limits of polynomial-time approximation.
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 A0, we construct an (a+e)-approximation algorithm A. The algorithm A runs in time of the order cek, where k is the number of clauses in the input formula and c is a constant depending on a. Thus we estimate the cost of improving a performance ratio. Similar constructions for MAX 2-SAT and MAX 3-SAT are also described. Taking known algorithms as A0 (for example, the Karloff-Zwick algorithm for MAX 3-SAT), we obtain particular upper bounds on the running time of A.

[ Full text is available on request ]

Back to the list of papers