### 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 A_{0}, 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 A_{0} (for example, the Karloff-Zwick algorithm for MAX 3SAT), we obtain particular upper bounds on the running time of A.

Original language | English |
---|---|

Pages (from-to) | 81-94 |

Number of pages | 14 |

Journal | Annals of Pure and Applied Logic |

Volume | 113 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 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

*Annals of Pure and Applied Logic*,

*113*(1-3), 81-94. https://doi.org/10.1016/S0168-0072(01)00052-5