Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
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.
| Язык оригинала | английский |
|---|---|
| Страницы (с-по) | 81-94 |
| Число страниц | 14 |
| Журнал | Annals of Pure and Applied Logic |
| Том | 113 |
| Номер выпуска | 1-3 |
| DOI | |
| Состояние | Опубликовано - 27 дек 2001 |
ID: 49829486