This preprint was accepted May 20, 1998
Contact:
E. Ya. Dantsin, M. Gavrilovich, E. A. Hirsch, and B. Yu. Konev
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 polynomial-time approximation).
Namely, we show how to construct an $(\alpha+\epsilon)$-approximation
algorithm $\A$ from a given polynomial-time $\alpha$-approximation
algorithm $\A_0$. The algorithm $\A$ runs in time of the order
$\phi^{\epsilon(1-\alpha)^{-1} K}$,
where $\phi$ is the golden ratio ($\approx 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$.