数理解析研究所講究録 1325 巻 2003 年 169-174

169

ASimpler Analysis of Goemans and Williamson’s
LP-relaxation for MAX SAT
Takao Asano ( 浅野孝夫 )Chuo University ( 中央大学 )Kasuga, Bunkyo-ku, Tokyo 112-8551
as ano@i se.chuo-u.ac.jp
Abstract. Asano and Williamson obtained two types of best approximation algorithms for MAX
SAT: one with best proven performance guarantee 0.7846 and the other with performance guaran0.8331 if aconjectured performance guarantee of 07977 is true in the Zwick’s algorithm. Both-relaxation for
mlgorithms are based on their sharpened analysis of Goemans and Wilhamson’s
MAX SAT. In this paper, we present an improved analysis which is simpler than the previous
analysis by Asano and Williamson. Furthermore, algorithms based on this analysis will play arole as abetter building block in designing an improved approximation algorithm for MAX SAT.
Actua.uy we can show an example that algorithms based on this analysis lead to approximation algorithms with performance guarantee 07877 and conjectured performance guarantee 0.8353 which
are slightly better than the best known corresponding performance guarantees 0.7846 and 0.8331
respectively.

$\mathrm{t}\mathrm{e}\mathrm{e}$$\mathrm{L}\mathrm{P}$1Introduction

for any truth assignment $x\in\{0,1\}^{2n}$ withis satisfied$x_{i}+x_{n+i}=1(i=1,2, \ldots, n)$ andassignment
atruthof$C_{j}(x)=1$
value
. The
if
is defined to be $Fc(x)= \sum_{C_{j}\in C}w(Cj)Cj(x)$ .
That is, the value of is the sum of the weightsof the clauses in satisfied by . Thus, thegoal of MAX SAT is to find an optimal truth
assignment (i.e., atruth assignment of maxikSAT,
mum value). We will also use
restricted version of the problem in which eachclause has at most literals.
Goemans and Williamson considered thefollowing LP relaxation (GW) of MAX SAT$C_{j}$MAX SAT is one of the most popular NP-hardproblems and stated as follows: given aset ofclauses with weights, find atruth assignmentthat maximizes the sum of the weights of thesatisfied clauses. More precisely, an instance of, where is aset
MAX SAT is defined byof boolean clauses such that each clauseis adisjunction of literals with apositive weight$w(C)$ .
Let $X=\{x_{1}, \ldots, x_{n}\}$ be the set ofboolean variables in the clauses of C. Aliteralis avariable $x\in X$ or its negation . For sim. Thus,
plicity we assume$\overline{X}=\{\overline{x}|x\in X\}=\{x_{n+1}, x_{n+2}, \ldots, x_{2n}\}$ and. We assume that no literals with the same variable appear more thanonce in aclause in C. For each $x_{i}\in X$ , let$x_{i}=1$ ( $x_{i}=0$ , resp) if
is true (false, resp ).
Then, $x_{n+i}=\overline{x}_{i}=1-x_{i}$ and aclause $C_{j}=$can be considered to be$(\mathrm{C}, w)$$\mathrm{C}$$C\in \mathrm{C}$$\overline{x}$$x_{n+ii}=\overline{x}(xi=\overline{x}n+i)$$X\cup\overline{X}=\{x_{1}, \ldots, x_{2n}\}$$x_{i}$

$x$

$x$

$x$

$\mathrm{C}$$\mathrm{M}\mathrm{A}\mathrm{X}$$\mathrm{a}$

$k$

[3]:
$\max$$\mathrm{s}.\mathrm{t}$.

$\sum_{C_{j}\in C}w(C_{j})z_{j}$$\sum_{i=1}^{k_{j}}y_{j_{j}}\geq z_{j}$$\forall C_{j}=x_{j_{1}}\vee\cdots\vee x_{j_{\mathrm{k}_{\mathrm{j}}}}\in \mathrm{C}$$y_{i}+y_{n+i}=1$$\forall i\in\{1,2, \ldots, n\}$$0\leq y_{i}\leq 1$$\forall i\in\{1,2, \ldots, 2n\}$$0\leq z_{j}\leq 1$$\forall C_{j}\in \mathrm{C}$$x_{j_{1}}\vee x_{j_{2}}\vee\cdots\vee x_{j_{k_{j}}}\in \mathrm{C}$onafunction$x=(x_{1}, \ldots, x_{2n})$ . Thus, $C_{j}=Cj(oe)=0$ or 1
$Cj=Cj(x)=1- \prod_{i=1}^{k_{j}}(1-xj:)$.

In this formulation, variables $y=(y:)$ corre-170$1-4^{-y}\leq f_{3}(y)\leq 4^{y-1}$

and varispond to the literalsC.
theclausestoables $z=$ (zj) correspond
Thus, variable $y_{i}=1$ if and only if $xi=1$ . Simis satisfied. The
ilarly, $z_{j}=1$ if and only if
first set of constraints implies that one of theliterals in aclause is true if the clause is satisformulation of this (GW) withfied and thus
$y_{i}\in\{0,1\}(\forall i\in\{1,2, \ldots, 2n\})$ and $zj\in\{0,1\}$
exactly corresponds to MAX SAT.
to thisUsing an optimal solution
LP relaxation, Goemans and Wiffiamson set
each variable $xi$ to be true with probability .
Then they showed that aclause $C_{j}=xj_{1}\vee$is satisfied by this random truth
assignment $x^{p}=y^{*}$ with probability$\{x_{1}, \ldots, x_{2n}\}$.

Note that $f_{l}(y_{i}^{*})+f\ell(y_{n+i}^{*})=1$ hold for $\ell=$$1,2$ and thathas to be chosen to satisfy $f_{3}(y_{i}^{*})+f_{3}(y_{n+i}^{*})=1$ . They then provedthat all the random truth assignments $x^{p}=$$f_{3}(y_{i}^{*})$$C_{j}$

obtained in thisandway have the expected values at least
lead to -approximation algorithms.
Asano and Williamson [1] sharpened theanalysis of Goemans and Williamson to prOvide more precise bounds on the probability ofwith litaclauseerals being satisfied (and thus on the expected
weight of satisfied clauses in ) by the ran$f_{l}(y^{*})=(f_{\ell}(y_{1}^{*}), \ldots, f_{l}(y_{2n}^{*}))$$\mathrm{I}\mathrm{P}$$\frac{3}{4}W^{*}$$\frac{3}{4}$$(\forall C_{j}\in \mathrm{C})$$(y^{*}, z^{*})$$y_{i}^{*}$$k$$C_{j}=xj_{1}\vee xj_{2}\vee\cdots\vee x_{j_{k}}$$\mathrm{C}_{k}$$x_{j_{2}}\vee\cdots\vee x_{j_{k_{\mathrm{j}}}}$

for each
dom truth assignment(and $\ell=1,2$ ). From now on, we assume
by symmetry, $xj:=xi$ for each $i=1,2,$
since $f\ell(x)=1-f\ell(\overline{x})$ and we can set $x:=$
if necessary. They considered clause $Cj=$
corresponding to the conrelaxstraint $y_{1}+y_{2}+\cdots+y_{k}\geq zj$ in theation (GW) of MAX SAT, and gave aboundbeon the ratio of the probability of clauseassignment
truth
the
by
randoming satisfied$x^{p}=f_{\ell}(y^{*})(\ell=1,2)$ to. Actually, they anwith
andmlyzed parametrized functions
asfollows:
defined$x^{p}=f_{l}(y^{*})$

$k$

$=$

$C_{j}(y^{*})$$1-(1-y_{j_{1}}^{*})(1-y_{j_{2}}^{*})\cdots(1-y_{j_{k_{j}}}^{*})$$k$$\ldots,$$\geq$$(1-(1- \frac{1}{k})^{k})z_{j}^{*}$.

$\overline{x}$$x_{1}\vee x_{2}\vee\cdots\vee x_{k}$This implies that the expected value $F(y^{*})$ of
obtained in
the random truth assignmentway
satisfies
this$y^{*}$$F(y^{*})= \sum_{C_{j}\in \mathrm{C}}w(C_{j})\mathrm{q}(y^{*})$$\mathrm{L}\mathrm{P}$$C_{j}$$z_{\dot{\tau}}^{*}$$f_{1}^{a}$$\geq$$\sum_{k\geq 1}(1-(1-\frac{1}{k})^{k})W_{k}^{*}\geq(1-\frac{1}{e})W^{*}$

where is the base of natural logarithm, $W^{*}=$
andis the set of clauses in with literals and,$f_{2}^{a}$$\frac{1}{2}\leq a\leq 1$

if $0 \leq y\leq 1-\frac{1}{2a}$$ay+1-a$$e$$W_{k}^{*}= \sum_{C_{j}\in C_{k}}w(Cj)z_{j}^{*}(\mathrm{C}_{k}$$\sum_{C_{j}\in C}w(C_{j})z_{j}^{*}$$f_{1}^{a}(y)=\{$$\frac{1}{2}$$W^{*}= \sum_{C_{j}\in C}w(C_{j})z_{j}^{*}\geq\hat{W}=\sum_{C_{j}\in C}w(C_{j})\hat{z}_{j}$for an optimal solution

formu$(1 - \frac{1}{e})\approx 0.632$ ,
SAT).
MAX
of
Since
lationthis is a0.632-appr0ximati0n algorithm.
Goemans and Williamson [3] also considered three other non-linear randomized rounding algorithms. In these algorithms, each variable $xi$ is set to be true with probability
defined as follows $(\ell=1,2,3)$ .
$(\hat{y},\hat{z})$to the$f_{1}(y)=\{$$\frac{1}{2}$$\frac{3}{4}y$if$0 \leq y\leq\frac{1}{3}$if$\frac{1}{3}\leq y\leq\frac{2}{3}$

if

$ay$

if

$\frac{1}{2a}\leq y\leq 1$,(1)$f_{2}^{a}(y)=(2a-1)y+1-a$ .

(2)

Then their results are the following [1].

Theorem 1The probability of $C_{j}=x_{1}\vee\cdots\vee$satisfied by the ranclom truth assignis
ment$x_{k}\in \mathrm{C}$$x^{p}=f_{1}^{a}(y^{*})=(f_{1}^{a}(y_{1}^{*}), \ldots, f_{1}^{a}(y_{2n}^{*}))$,$C_{j}(f_{1}^{a}(y^{*}))=1- \prod_{i=1}^{k}(1-f_{1}^{a}(y_{1}^{*}.))\geq\gamma_{k^{Z}j}^{a*}$, wherein Eq. (1) andfor$\frac{1}{9}$$\leq a\leq 1$.

$f_{1}^{a}$is thefunction defined$\frac{2}{3}\leq y\leq 1$$a$$f_{2}(y)=(2a-1)y+1-a$$1- \frac{1}{2a}\leq y\leq\frac{1}{2a}$$\mathrm{I}\mathrm{P}$$f\ell(y_{i}^{*})$$\frac{3}{4}y+\frac{1}{4}$

if

$k$

$\mathrm{C}$$\gamma_{k}^{a}=\{$$( \frac{3}{4}\leq a\leq\frac{3}{\sqrt[\mathrm{a}]{4}}-1)$$\min\{\gamma_{k,1}^{a},\gamma_{k,2}^{a}\}$if $k=1$
if$k\geq 2$

(3)

171

Let

with

$y_{a}= \frac{1}{a}-\frac{1}{2}$$\gamma_{k,1}^{a}$$1- \frac{1}{2}a^{k-1}(1-\frac{1-\frac{1}{2a}}{k-1})^{k-1},$

$=$

$(4)$

.

(8)

Then the other parametrized function$f_{4}^{a}$is de-

fined as follows:$\gamma_{k,2}^{a}$$1-a^{k}(1- \frac{1}{k})^{k}$

$=$

.

(5)

Thus, the expected valueof the ran$x^{p}=f_{1}^{a}(y^{*})$
assignment
truth
dom
satisfies$F(f_{1}^{a}(y^{*}))$$F(f_{1}^{a}(y^{*})) \geq\sum_{k>1}\gamma_{k}^{a}W_{k}^{*}$$f_{4}^{a}(y)=\{$.

$ay+1-a$

if $0\leq y\leq 1-y_{a}$$\frac{a}{2}y+\frac{1}{2}-\frac{a}{4}$

if $1-y_{a}\leq y\leq y_{a}$if $y_{a}\leq y\leq 1$ .

$ay$Theorem 2The probability of $C_{j}=x_{1}\vee\cdots\vee$satisfied by the randorrn truth assignis
ment$x_{k}\in \mathrm{C}$$x^{p}=f_{2}^{a}(y^{*})=(f_{2}^{a}(y_{1}^{*}), \ldots, f_{2}^{a}(y_{2n}^{*}))$

(9)
Thus,

$f_{3}^{a}(y)+f_{3}^{a}(1-y)=1$$y)=1$ hold for $0\leq y\leq 1$ . Furthermore,,$f_{4}^{a}$$f_{3}^{a}( \frac{1}{2})=f_{4}^{a}(\frac{1}{2})=\frac{1}{2}$$f_{4}^{a}$$f_{3}^{a}$, where
(2)
Eq.
and
in

for

$\frac{1}{2}\leq a\leq 1$$\delta_{k}^{a}=1-a^{k}$$f_{2}^{a}$is the function defined$f_{3}^{a}$and are both continuous functions which are.
increasing with . Thus,
We have the following theorems for the twoand .
parameterized functions$y$$C_{j}(f_{2}^{a}(y^{*}))=1- \prod_{i=1}^{k}(1-f_{2}^{a}(y_{i}^{*}))\geq\delta_{k}^{a}z_{j}^{*}$

and$f_{4}^{a}(y)+f_{4}^{a}(1-$Theorem 4For $\frac{1}{2}\leq a\leq L_{2}^{e}=0.82436,$ thebeing
probability of$x^{p}=$
satisfied by the random truth assignmentis$C_{j}=x_{1}\vee x_{2}\vee\cdots\vee x_{k}\in \mathrm{C}$(1$\frac{2-\frac{1}{a}}{k}$
一

).

(6)

Thus, the expected valueof the random truth assignment $x^{p}=f_{2}^{a}(y^{*})$ satisfies$F(f_{2}^{a}(y^{*}))$$F(f_{2}^{a}(y^{*})) \geq\sum_{k>1}\delta_{k}^{a}W_{k}^{*}$.

andTheorem 3For
defined inhold for all $k\geq 3$ and forand (6),all rnith $\frac{1}{2}<a<1$ . For $k=1,2,$
hold.
$Eqs.(\mathit{3})$$\delta_{k}^{a}$$\gamma_{k}^{a}$$f_{3}^{a}(y^{*})=(f_{3}^{a}(y_{1}^{*}), \ldots, f_{3}^{a}(y_{2n}^{*}))$

Cj(f3a(y 勺)
where$f_{3}^{a}$$=1- \prod_{i=1}^{k}(1-f_{3}^{a}(y_{i}^{*}))\geq\zeta_{k}^{a}z_{j}^{*},$

is the function defined in Eq. (7) and$\zeta_{k}^{a}=\{$

if $k=1$.
if$a1- \frac{1}{4}a^{k-2}$$k\geq 2$$\gamma_{k}^{a}>\delta_{k}^{a}$$a$$\gamma_{k}^{a}=\delta_{k}^{a}$$( \gamma_{1}^{a}=\delta_{1}^{a}=a, \gamma_{2}^{a}=\delta_{2}^{a}=\frac{\overline{\delta}}{4})$Asano and Williamson have not considered aparametrized function of . In this section weof andconsider aparametrized function
show that it has better performance thanand . Furthermore, its analysis (proof) is
simpler. We also consider ageneralization ofbothand and show that it has also betterand .
performance than, let
be defined as follows:For$f_{3}$$f_{3}$$f_{3}^{a}$(11)

Thus, the expected value $F(f_{3}^{a}(y^{*}))$ of the random truth assignment $x^{p}=f_{3}^{a}(y^{*})$ sahsfies$F(f_{3}^{a}(y^{*})) \geq\sum_{k>1}\zeta_{k}^{a}W_{k}^{*}$

2Main Results

(10)

.

Theorem 5For $L^{e}2=0.82436$ $\leq a\leq 1$ , theprobability of $Cj=x1\vee x_{2}\vee\cdots\vee xk\in \mathrm{C}$ being
sahsfied by the random truth assignment $x^{p}=$is$f_{4}^{a}(y^{*})=(f_{4}^{a}(y_{1}^{*}), \ldots, f_{4}^{a}(y_{2n}^{*}))$$f_{1}^{a}$$f_{2}^{a}$$f_{1}^{a}$$C_{j}(f_{4}^{a}(y^{*}))=1- \prod_{i=1}^{k}(1-f_{4}^{a}(y_{i}^{*}))\geq\eta_{k^{Z}j}^{a*},$(12)$f_{2}^{a}$$f_{2}^{a}$$f_{1}^{a}$$\frac{1}{2}\leq a\leq 1$

where$f_{4}^{a}$is the function defined in Eq.(9) and$f_{3}^{a}$$a$$\eta_{k}^{a}=\{$$1-T^{T}4a\Gamma^{y}a$if$\min\{\eta_{k,1}^{a},\eta_{k,2}^{a}, \eta_{k,3}^{a}\}$$0 \leq y\leq\frac{1}{2}$(7)$f_{3}^{a}(y)=|\{$$\mathrm{L}_{4a}^{2}4a\mathit{1}_{-}^{y}$if$\frac{1}{2}\leq y\leq 1$.

$\eta_{k,1}^{a}=1-a^{k}(1-\frac{1}{k})^{k}$,

if $k=1$
if$k\geq 2$(13)$\eta_{k,2}^{a}=1-\frac{a^{k-2}}{4}$

,

172

$\eta_{k,3}^{a}=1-\frac{a^{k}}{2}(1-\frac{1-y_{a}}{k-1})^{k-1}$$(\eta_{k,1}^{a}=\gamma_{k,2}^{a}, \eta_{k,2}^{a}=\zeta_{k}^{a})$. The expected valueof the random truth assignment.
satisfies$F(f_{4}^{a}(y^{*}))$$f_{4}^{a}(y^{*})$$x^{p}=$$F(f_{4}^{a}(y^{*})) \geq\sum_{k>1}\eta_{k}^{a}W_{k}^{*}$$\eta_{k}^{a}$$\zeta_{k}^{a}$$y_{1}^{*}+y_{2}^{*}+\cdots+y_{k}^{*}\geq z_{j}^{*}$

in therelaxation (GW) of MAX SAT, wewill show that$\mathrm{L}\mathrm{P}$, andTheorem 6For
defined in$Eqs.(S),$(11), and (13), we have the following.
$\gamma_{k^{f}}^{a}\delta_{k}^{a},$Proof of Theorem 4. Noting that clause$C_{j}=x_{1}\vee x_{2}\vee\cdots\vee x_{k}$ corresponds to the constraint(14)$(\theta),$

1. If $\frac{1}{2}\leq a\leq L_{2}^{e}=0.82436$ , thenhold for all $k\geq 3$ .

$C_{j}(f_{3}^{a}(y^{*}))=1- \prod_{i=1}^{k}(1-f_{3}^{a}(y_{i}^{*}))\geq\zeta_{k}^{a}z_{j}^{*}$$\zeta_{k}^{a}>$If $k=1$ , then we have$\gamma_{k}^{a}>\delta_{k}^{a}$

2. If $L_{2}^{e}=0.82436$ $\leq a\leq 1$ , thenhold for all $k\geq 3$ .

.

$C_{j}(f_{3}^{a}(y^{*}))=f_{3}^{a}(y_{1}^{*})\geq ay_{1}^{*}\geq az_{j}^{*}=\zeta_{1}^{a}z_{j}^{*}$$\eta_{k}^{a}>\gamma_{k}^{a}>$$\delta_{k}^{a}$

3. For $k=1,2,$$\gamma_{k}^{a}=\delta_{k}^{a}=\zeta_{k}^{a}$$a\leq L_{2}^{e}=0.82436$, andhold if $L_{2}^{e}=0.82436$$\zeta_{k}^{a}=\eta_{k}^{a}=a,$hold if$\frac{1}{2}\leq$$\gamma_{k}^{a}=\delta_{k}^{a}=\eta_{k}^{a}$by Lemma 1and inequality (14).
Next suppose $k\geq 2$ . By symmetry, we
assumeand consider two;and Case
cases as follows: Case 1:
2:. Since all
Case 1:$(i=1,2, \ldots, k)$ , we have $f_{3}^{a}(y_{i}^{*})=1--$$y_{1}^{*}\leq y_{2}^{*}\leq\cdots\leq y_{k}^{*}$$0 \leq y_{k}^{*}\leq\frac{1}{2}$$\leq a\leq 1(\gamma_{1}^{a}=\delta_{1}^{a}=$$\gamma_{2}^{a}=\delta_{2}^{a}=\zeta_{k}^{a}=\eta_{k}^{a}=\frac{3}{4})$.

$\frac{1}{2}<y_{k}^{*}\leq 1\mathrm{r}$$0 \leq y_{k}^{*}\leq\frac{1}{2}$$y_{\dot{\iota}}^{*} \leq_{a}\frac{1}{2}$In this paper, we first give aproof of Theorem 4. It is very simple and we use only thefollowing lemma.

and$1-f_{3}^{a}(y_{i}^{*})= \frac{a}{(4a^{2})^{y}}\dot{.}$Lemma 1If $\frac{1}{2}\leq a\leq L_{2}^{e}=0.82436$ , then$f_{3}^{a}(y)\geq ay$.

. Then its derivaProof. Let. Thus, $g’(y)$ istive is$g’(1)=a(\ln(4a^{2})-1)\leq$
increasing with and, since $\ln(4a^{2})\leq\ln(4(^{L_{2}^{e}})^{2})=1$ . This implies that $g’(y)\leq 0$ for all $0\leq y\leq 1$ andthat $g(y)$ is decreasing with $0\leq y\leq 1$ . Thus,$g(y)$ takes aminimum value at $y=1$ , i.e.,. Thus, we have$(4a^{2})^{y}$:$C_{j}(f_{3}^{a}(y^{*}))=1- \prod_{i=1}^{k}(1-f_{3}^{a}(y_{i}^{*}))$$g(y) \equiv\frac{\mathrm{q}a^{-\sigma}}{4n}.-ay$

$=$

1-

$\prod_{i=1}^{k}\frac{a}{(4a^{2})^{y^{\mathrm{r}}}}\dot{.}=1-\frac{a^{k}}{(4a^{2})^{\sum_{=1}^{k}y^{\mathrm{r}}}}\dot{.}\dot{.}$$g’(y)=\ln(4a^{2})^{\llcorner_{4a}^{a^{-[perp]^{y}}}}4.-a$$y$$\geq$$0$$g(y)= \mathrm{L}^{4a^{2y}}4a[perp]-ay\geq g(1)=\frac{4a^{2}}{4a}-a=0$.

$\frac{1}{2}\leq y\leq 1$$0 \leq y\leq\frac{1}{2}$$=$$1- \frac{a}{(4a^{2})^{y}}-ay$$=$$- \frac{(4a^{2})^{1-y}}{4a}+a(1-y)+1-a$$=$

where the first inequality follows by inequality(14), and the second inequality follows fromthe fact that 1
is aconcave function

in$0\leq z_{j}^{*}\leq 1$.

.
. Suppose
Case 2:
Then $1-f_{3}^{a}(y_{i}^{*})\leq a(i=1,2, \ldots, k-1)$ and wehave$\frac{1}{2}<y_{k}^{*}\leq 1$

cj(f3a(y 勺)$-g(1-y)+1-a$$-g( \frac{1}{2})+1-a=\frac{1-a}{2}\geq 0$

since $g(y)$ is decreasing and $g(1-y) \leq g(\frac{1}{2})=$.
for$\frac{1-a}{2}$$\frac{1}{2}\leq 1-y\leq 1$$\blacksquare$$z_{j}^{*}<y_{k}^{*}$$=1- \prod_{i=1}^{k}(1-f_{3}^{a}(y_{i}^{*}))$$\geq 1-a^{k-1}(1-\frac{(4a^{2})^{y_{k}^{*}}}{4a})$$\geq$,$- \frac{a^{k}}{(4a^{2})^{z_{j}}}$Now we are ready to prove the lemma. For, we have $f_{3}(y)-ay=g(y)=\mathrm{L}_{4a}^{4a^{2y}}[perp]-$$ay\geq 0$ . For, we have$f_{3}(y)-ay$$1- \frac{a^{k}}{(4a^{2})^{z_{j}^{*}}}\geq(1-\frac{a^{k}}{4a^{2}})z_{j}^{*}=\zeta_{k}^{a}z_{j}^{*}$$\geq 1-a^{k-1}(1-\frac{(4a^{2})^{z_{\mathrm{j}}^{*}}}{4a})$173$\geq$

that 1$(1-a^{k-1}(1- \frac{(4a^{2})}{4a}))z_{j}^{*}$$z_{j}^{*}\leq 1$$=$$(1-a^{k-1}(1-a))z_{j}^{*}$$\geq$$(1- \frac{a^{k-2}}{4})z_{j}^{*}=\zeta_{k}^{a}z_{j}^{*}$is aconcave function in $0\leq$.

$\blacksquare$

Proofs of Theorems 5and 6. Proofs ofTheorems 5and 6are almost similar to ones in
Asano and Williamson [1]. In this sense, proofs
may be alittle complicated, however, they canbe done in asystematic way. We omit details.

,

where the second inequality follows by, the third inequality by the fact that 1$- \frac{a^{k}}{(4a^{2})^{j}z^{*}}$$z_{j}^{*}<$$y_{k}^{*}$$a^{k-1}(1-\mathrm{L}_{4a}4a^{2^{z^{\mathrm{B}}}}\llcorner^{j})$$\leq 1$.

is aconcave function in$\blacksquare$-$0\leq$, and the forth inequality by $a(1-a)\leq$$\frac{z_{1}}{4}j*$. If $y_{k-1}^{*}>$
Thus, we can assume, then 1 $-f_{3}^{a}(y_{i}^{*})\leq a(i=1,2, \ldots, k-2)$ ,$z_{\dot{r}}^{*}\geq y_{k}^{*}$$\frac{1}{2}$$1-f_{3}^{a}(y_{i}^{*})=1- \mathrm{L}_{4a}^{4a^{\mathit{1}}}[perp]^{y}.\cdot\leq\frac{1}{2}(i=k-1, k)$$z_{j}^{*}\leq 1$, and, and we have$C_{j}(f_{3}^{a}(y^{*}))=1- \prod_{i=1}^{k}(1-f_{3}^{a}(y_{i}^{*}))$$\geq$$1-a^{k-2}( \frac{1}{2})^{2}=1-\frac{a^{k-2}}{4}$$\geq$$(1- \frac{a^{k-2}}{4})z_{j}^{*}=\zeta_{k}^{a}z_{j}^{*}$

3Improved Approximation Algorithms
In this section, we briefly outline our improved
appproximation algorithms for MAX SAT basedon ahybrid approach which is described in detail in Asano and Wiffiamson [1]. We use asemidefinite programming relaxation of MAX
SAT which is acombination of ones given by
Goemans and Williamson [4], Feige and Goemans [2], Karloff and Zwick [6], Halperin and
Zwick [5], and Zwick [7]. Our algorithms pickthe best solution returned by the four algo
in Goemans
rithms corresponding to (1)algorithm
and WiUiamson [3], (2) MAX
andHalperin[2]
orofof Feige and Goemans
algorithm of Karloff
Zwick [5], (3) MAX
and Zwick [6] or of Halperin and Zwick [5],and (4) Zwick’s MAX SAT algorithm with aconjectured performance guarantee 07977 [7].
The expected value of the solution is at least as
good as the expected value of an algorithm thatuses Algorithm (i) with probability $pi$ , where$f_{3}^{a}$Thus, we can assume.

$y_{k-1}^{*} \leq\frac{1}{2}$$2\mathrm{S}\mathrm{A}\mathrm{T}$. Then, since

1 $-f_{3}^{a}(y_{i}^{*})= \frac{a}{(4a^{2})^{v_{i}}}(i=1,2, \ldots, k-1)$ , wehave
$C_{j}(f_{3}^{a}(y^{*}))=1- \prod_{i=1}^{k}(1-f_{3}^{a}(y_{i}^{*}))$$3\mathrm{S}\mathrm{A}\mathrm{T}$$p_{1}+p_{2}+p_{3}+p_{4}=1$$=$$1- \frac{a^{k-1}}{(4a^{2})^{\sum_{=1}^{k-1}y}}.\cdot\dot{.}.(1-\frac{(4a^{2})^{y_{k}^{*}}}{4a})$$\geq$$1- \frac{a^{k-1}}{(4a^{2})^{z_{j}^{\mathrm{r}}-y_{k}^{*}}}(1-\frac{(4a^{2})^{y_{k}^{*}}}{4a})$.

Our first algorithm pick the best solution
returned by the three algorithms correspondin Goemans and Williamson [3],ing to (1)algorithm(2) Feige and Goemans’s MAX[2], and (3) Karloff and Zwick’s MAX
algorithm [6] (this implies that $p4=0$ ). From
the arguments in Section 3, the probability thatis satisfied by Algorithm (1)aclauseis defined in Eq $.(11)$ .
, whereis at least
Similarly, from the arguments in $[4, 2]$ , theis satisfied
probability that aclause
by Algorithm (2) is$f_{3}^{a}$$2\mathrm{S}\mathrm{A}\mathrm{T}$$3\mathrm{S}\mathrm{A}\mathrm{T}$$=$$1- \frac{a^{k-1}}{(4a^{2})^{z_{j}^{*}}}(4a^{2})^{y_{k}^{*}}(1-\frac{(4a^{2})^{y_{k}^{*}}}{4a})$$\geq$$1- \frac{a^{k-1}}{(4a^{2})^{z_{j}^{*}}}a=1-\frac{a^{k}}{(4a^{2})^{z_{\mathrm{j}}^{*}}}$$C_{j}\in \mathrm{C}_{k}$$\cdot$$\zeta_{k}^{a}z_{j}^{*}$$\geq$$(1- \frac{a^{k-2}}{4})z_{j}^{*}=\zeta_{k}^{a}z_{j}^{*}$

by inequality (14),$u(1- \frac{u}{4a})\leq a$ with,$\zeta_{k}^{a}$$Cj\in \mathrm{C}_{k}$$(4a^{2})^{y_{k}^{*}}(1-\zeta 4a_{4a}^{2\underline{y_{k}^{l}}}\Delta)=$$y_{k}^{*}\leq z_{j}^{*},$$u=(4a^{2})^{y_{k}^{*}}$, and the factat least 0.93109$\cdot\frac{2}{k}z_{j}^{*}$

for $k\geq 2$ ,

174

and at least

for $k=1$ .

$0.97653z_{j}^{*}$

algorithms are based on the nuIVIAX
merical evidence [5] .
Suppose finally that we use two algorithms
in Goemans and Williamson [3] and (4)(1)
Zwick’s MAX SAT algorithm with aconjectured performance guarantee 0.7977 [7]. If we
set $a=0.907180$ , $p_{1}=0.343137$ and $p_{4}=$0.656863 $(p_{2}=p_{3}=0)$ , then the probability ofwith literals being satisfied can beclausefor each $k\geq 1$ .
at least
beshown toThus, we can obtain a08353-appr0ximati0nalgorithm for MAX SAT if aconjectured performance guarantee 0.7977 is true in Zwick’s
MAX SAT algorithm [7].
$3\mathrm{S}\mathrm{A}\mathrm{T}$$)$By an analysis obtained by Karloff and Zwick[6] and an argument similar to one in [4], theis satisfied byprobability that aclause
Algorithm (3) is at least$Cj\in \mathrm{C}_{k}$at least

and at least

for $k\geq 3$ ,$\frac{3}{k}\frac{7}{8}z_{j}^{*}$$0.87856z_{j}^{*}$

for $k=1,2$ .

Suppose that we set $a=0.74054$ , $p_{1}=0.7861$ ,$p_{2}=0.1637$ , and $p_{3}=0.0502$ $(p_{4}=0)$ . Then$ap_{1}+0.97653p_{2}+0.87856p_{3}$$\geq$

0.7860

for $k=1$ ,$\frac{3}{4}p_{1}+0.93109p_{2}+0.87856p_{3}$$\geq$

0.7860

for $k=2$ ,$\zeta_{k}^{a}p_{1}+\frac{2\cross 0.93109}{k}p_{2}+\frac{3}{k}\frac{7}{8}p_{3}$$\geq$

0.7860

for $k\geq 3$ .

Thus this is a07860-appr0ximati0n algorithm.
Note that, under same conditions in Asano andWilliamson [1], the algorithm picking the bestsolution returned by the three algorithms corin Goemans
withresponding to (1)[2],Goemans
and
(2)
Feige
[3],
Williamson
and
the
only
achieves[6]and (3) Karloff and Zwick
performance guarantee 07846.
Suppose next that we use three algorithms
in Goemans and Williamson [3], (2)(1)
algorithm
Halperin and Zwick’s MAX
MAX
Zwick’sand(3)
Halperin[5], andalgorithm [5] instead of Feige and Goemans[2] and Karloff and Zwick [6]. If we set $a=$
0.739634, $p_{1}=0.787777$ , $p_{2}=0.157346$ , and$p_{3}=0.054877$ then we have
$a= \frac{3}{4}$$f_{1}^{a}$$f_{3}^{a}$$2\mathrm{S}\mathrm{A}\mathrm{T}$$3\mathrm{S}\mathrm{A}\mathrm{T}$$ap_{1}\dotplus 0.9828\mathrm{p}_{2}+0.9197p_{3}$$\geq$

0.7877

for $k=1$ ,$f_{4}^{a}$$C_{j}$$k$$0.8353z_{j}^{*}$

References[1] T. Asano and$\mathrm{D}.\mathrm{P}$. Williamson, Improved ap-

proximation algorithms for MAX SAT, Journalof Algorithms 42, pp.173-202, 2002.
[2] U. Feige and M. X. Goemans, Approximating
the value of two prover proof systems, with ap-.
and MAX DICUT, In
plications to MAX
on Theory of ComSymposium
Proc. 3rd Israel
puting and Systems, PP. 182-189, 1995.
[3] M. X. Goemans and D. P. Wiffiamson, New
3/4-approximation algorithms for the maximum satisfiabihty problem, SIAM Journal on
Discrete Mathematics 7, pp. 656-666, 1994.
[4] M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum
cut and satisfiability problems using semidefinite programming, Journal of the $ACM42,$ .
1115-1145,1995.
[5] E. Halperin and U. Zwick, Approximation algorithms for MAX 4-SAT and rounding procedures for semidefinite programs, In Proc. 7th
MPS Conference on Integer Programming andCombinatorial Optimization, LNCS 1610, pp.
202-217, 1999.
[6] H. Karloff and U. Zwick, A7/8-apprOximatiOn, In Proc. 38th IEEE
mlgorithm for MAX
Foundahons
theon
Symposiumof Computer
Science, PP. 406-415, 1997.
[7] U. Zwick, Outward rotations: atool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and
Symposiumother problems, In Proc.
on the Theory of Computing, pp. 679-687, 1999.
$2\mathrm{S}\mathrm{A}\mathrm{T}$$\mathrm{p}\mathrm{p}$$3\mathrm{S}\mathrm{A}\mathrm{T}?$$\frac{3}{4}p_{1}+0.9309p_{2}+0.9197p_{3}$$\geq$

0.7877

for $k=2$ ,$\zeta_{k}^{a}p_{1}+\frac{2\cross 0.9309}{k}p_{2}+\frac{3}{k}\frac{7}{8}p_{3}$$\geq$

0.7877$\mathit{9}\mathit{1}stACM$

for$k\geq 3$.

Thus we have a07877-appr0ximati0n algorithm
for MAX SAT (note that the performance guarand
antees of Halperin and Zwick’s MAX$2\mathrm{S}\mathrm{A}\mathrm{T}$