###
Petersburg Department of Steklov Institute of Mathematics

#
PREPRINT 14/1998

E. Dantsin, M. Gavrilovich, E. Hirsch, and B. Konev
##
APPROXIMATION ALGORITHMS FOR MAX SAT:
A BETTER PERFORMANCE
RATIO AT THE COST OF A LONGER RUNNING TIME

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$.

Back to all preprints

Back to the Petersburg Department of
Steklov Institute of Mathematics