APPROXIMATION ALGORITHMS FOR MAX SAT: A BETTER PERFORMANCE RATIO AT THE COST OF A LONGER RUNNING TIME

Abstract

We describe approximation algorithms for (unweighted) MAX SAT with performance ratios arbitrarily close to 1 (in particular, when performance ratios exceed the limit of polynomialtime approximation). Namely, we show how to construct an (# + #)-approximation algorithm A from a given polynomial-time #-approximation algorithm A 0 . The algorithm A runs in time of the order # #(1-#) -1 K , where # is the golden ratio (# 1.618) and K is the number of clauses in the input formula. Thus we estimate the cost of improving a performance ratio. Similar constructions for MAX 2SAT and MAX 3SAT are described too. We apply our constructions to some known polynomial-time algorithms taken as A 0 and give upper bounds on the running time of the respective algorithms A. 1 Introduction In the MAX SAT problem we are given a Boolean formula represented by a set of clauses, and we seek a truth assignment that maximizes the number of satisfied clauses. An #-approximation algorithm for MAX SAT i...