MAX SAT approximation beyond the limits of polynomial-time approximation

Evgeny Dantsin, Michael Gavrilovich, Edward A. Hirsch, Boris Konev

Research output

20 Citations (Scopus)

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

Original languageEnglish
Pages (from-to)81-94
Number of pages14
JournalAnnals of Pure and Applied Logic
Volume113
Issue number1-3
DOIs
Publication statusPublished - 27 Dec 2001

Scopus subject areas

  • Logic

Fingerprint Dive into the research topics of 'MAX SAT approximation beyond the limits of polynomial-time approximation'. Together they form a unique fingerprint.

  • Cite this