WIXLIB

Algon!thmsThewardfor ik%ximurnabovediscussionmodificationsin forMAX2SAT,forandthereMAXexistsany of theseaprob-et al. [unpublishedfor MAXDICUTCUTstraightfom--improvementsthatet al. 1992]. Bellaremanuscript]have shown that c is as small as 83/84for MAX2SAT. Since bidirectedinstances of MAXinstan cesthatMAXso it is knowna c-approximationP NP [Arora1119not lead to significantFurthermore,SNP-hardc 1 such thatlems wouldProblemson the worst-caseof our techniqueMAXDICLJTCut and SatisfiabilityCUT and 95/!16are equivalenttoalsoappliestoMAXDIC JT.Since the appearanceof an abstract of this paper, Feigehave extended our techniqueto yield a .931 -approximation2SAT and a .859-approximationinite programmingand similaralgorithmroundingand Goemans [1995]algorithmfor MAXfor MAX DICUT.By using semidefideas, Karger -et al. [1994] have beenable to show how to color a k-colorablegraph with 0( n* – ‘3’( 1))) colors inpolynomialtime. Frieze and Jerrum[1996] have used the techniqueto deviseapproximationalgorithmsfor the maximumk-way cut problemthat improve onthe best previously[1995] apply ideasseems likelythatknown 1 – l/kfrom this paperthe techniquesperformanceguarantee.to the “betweenness”in this paperwilldesigningapproximationalgorithms.We expect that in practicethe performancebetterthanthecomputationala numberworst-casebounds.experimentsof differentwithtypeshavethe MAXCUTof random.96 of the optimalsolution.A preliminaryversion of thispapercontinueof ourWegraphsChor and Sudanproblem.Thus, itto provealgorithmsperformedsomealgorithmwhichthe algorithm[Goemanswillusefulbe muchpreliminaryshow thatis usuallyand Williamsonincmwithin1994a]pre-sented a methodto obtaindeterministicversions of our approximationalgorithm with the same performanceguarantees.However,the method given hada subtleerror,Ramesh[1995]as was pointeddocumenttheschem e for our algorithms.The paper is structuredMAXCUTin Sectionoutto us by severalerroras follows:andproposeWe present2, and its analysisresearchers.theirownthe randomizedin Section3. WeMahajanandderandomizaticmalgorithmelaborateforon oursemidefiniteprogrammingbound and its relationshipwith other work on theMAXCUT problemin Section 4. The quality of the relaxationis investigatedin Section 5, and computationalresults are presentedin Section 6. In Section 7,we show how to extendSAT,openthe algorithmMAX DICUT,and otherlproblems in Section 8.2. The Randomizedto an algorithmproblems.ApproximationWe concludeAlgorithmfor MXXforwithMAX2SAT,a few remarksMAXandCUTn} and nonnegativeweights Wij jiGiven a graph with vertex set V {1,.,for each pair of verticesi and j, the weightof the maximumcut w(S, S) Ngiven by the followinginteger quadraticprogram:Maximize ,wij(l-.Yiyj)1 J(Q)subjectto: yi c { – 1, 1}Vi G V.

M. X. GOEMANS AND D. P. WILLIAMSON1120Tosee this, (S,S)note i thattheset S {il yi 1} correspondsto a cutSince solving this integerquadraticprogramis NP-complete,relaxationsof (Q). Relaxationsof (Q) are obtainedby relaxingconstraintsthus,alloptimalof (Q),possiblevalueof weightj W j(l – Yiyj).andextendingsolutionsofof the relaxationthe(Q)objectivearefunctionfeasibleis an upperforboundwe considersome of theto thethelargerrelaxation,on the optimalspace;andvaluetheof (Q).We can interpret(Q) as restrictingYi to be a l-dimensionalvector of unitnorm. Some very interestingrelaxationscan be definedby allowingyi to be amultidimensionalvectorUi of unit Euclideannorm.Since the linearspacespanned by the vectorsvectorsbelongto R”n-dimensionaluniting optimizationjectivefunctionUi has dimension(orsphereat mostRm for someS. (or S forproblemis indeedin such a way thatn, we can assumethatthesem n), or more preciselyto them s n). To ensure that the result-a relaxation,we need to definethe obit reduces to i. j Wij(l – yiyj) in thecase of vectorslying in a l-dimensionalspace. Thereare several naturalways of guaranteeingthis property.For example, one can replace (1 – yiyj) by(1 – u, “ Uj), whereand Vj. The resultingu, “ Uj representsrelaxationMaximize(P)subjectWe will showprogramming.MAXCUTtheinneris denoted , Wij(lZ Jproduct(ordotproduct)of iby (P):-U, “ ‘j)Vito: Ui G S.in Section 4 that we can solve this relaxationWe can now present our simple randomizedE V.using semidefinitealgorithmfor theproblem.(1) Solve (P), obtainingan optimalset of vectors Ui.(2) Let r be a vector uniformlydistributedon the unitsphereS.(3) Set S {il.ZJi “r O}.In other words, we choose a randomhyperplanethroughits normal)and partitionthe verticesinto those vectorsthe origin (withthat lie “above”r astheplane (i.e., have a nonnegativeinner product with r) and those that lie “below”it (i.e., have a negative inner product with r). The motivationfor this randomized step comes from the fact that (P) is independentof the iontoa setofvectorsresultsinasolutionwith the same objectivevalue.Let W denotethe value of the cut producedin this way, and E[W]itsexpectation.We will show in Theorem3.1 in Section 3 that, given any set ofvectors Ui S., the expected weight of the cut defined by a random hyperplaneisarccos( ui - uj )E[W]We willalso show in TheoremE[W] wiji jT3.3 that a“ : wij(l1 ]– Ui”uj),

Algorithmsfor MaximumCut and Satisjiability1121Problemswhere26 ”— .878.0%.If Z; is the optimalthe relaxationalgorithm(P),is equalvaluethen%- 1 – Cos 8of the maximumcut and Z;since the expectedto E[ W] aZjweight aZ c,is the optimalthe algorithmassumeprogramby thma (Z;willin polynomialSection(P) is equivalentto a semidefiniteprogram.an algorithmfor semidefiniteprogramming,E 0, a set of vectors Ui’s of valuethe inputsize and log l/ .OnequalIn4, weshowproducea cutTheof expectedpointtimle.thattheThen we will show that,we can obtain,for anygreater than 2 – E in timethese approximatelyoptimal– e) z ( a – e )Z c.ofby thehas a performanceguaranteeof a for the MAXCUT problem.We must argue that the algorithmcan be implementedWevalueof the cut generatedvalueon the unitpolynomialvectors,greatersphereinthethanorS. can begeneratedby drawingn values xl, X2, ., x. independentlyfrom the standardnormaldistribution,and normalizingthe vector obtained(see Knuth[1981, p.130]); for our purposes,there is no need to normalizethe resultingvector x.The standardnormaldistributioncan be simulatedtion betweenO and 1 (see Knuthrandomized( a – e)-approximation3. Analysisusingthe uniformIn this section,we analyzecase and thenand the generalizationthe performanceconsiderto negativeof the algorithm.the case in whichedge weights.We firstthe maximumWe concludea new formulationfor the MAXCUT problem.u.} be any vectors belongingto S., and let E[W]Let {ul,.,value of the cutprevicms section.THEOREMw(S, ) producedby theWe start by characterizingaanalyzecut is largethis sectionwithbe the expectedrandomizedalgorithmgiven in thethe expected value of the cut.3.1a vector r drawn uniformlyof expectationthatE[W’]where sgn(x)the followingLEMMAis thusof the Algorithmthe generalGivenlinearitydistribu-[1981, p. 117]). The algorithmalgorithmfor MAXCUT, 1 if x 0,lemma. wiji jfrom“ pr[sgn(uiandthe unit“ r)– 1 otherwise.sphereS., we know sgn( j“ r)],Theorem3.1 is thus3.2Pr[sgn(ui”r)# sgn(uj”r)] arccos(uic uj).by theimpliedby

M. X. GOEMANS AND D. P. WILLIAMSON1122PROOF.Arestatementof thelemmais thattheprobabilitytherandomhyperplaneseparates the two vectors is directlyproportionalto the angle between the two vectors; that is, it is proportionalto the angle f3 arccos( Ui “ Uj).By symmetry,Pr[sgn(ui”r-) # sgn( Uj “ r)] 2 Pr[ Ui . r 0, Uj” r O]. The set{r:u,. r 0,Uj “ r O} correspondsdihedralangledigon of anglet9/2mr 0,Ourto the intersectiontimesthe measureof thefullsphere.Uj . r O] t9/2T, and the lemma follows.maintheoremapplied to vectorshas a performanceis the following:Theoremthe followinglemma3.4.PROOF.words,above,Pr[ui.this theoremthe algorithm20m 1 – Cos 19”For of the– Ui”uj).of Wij, the resultfollowsfromto y vi oUj.– 1 s y s 1, 1 arccos(y)\mfora followscos 6 y. See Figurequality ,wij(lc j3.1 and the nonnegativityappliedThe expressionof variablesThewhose3.3E[W’]LEMMAotherthan Z: – implies that . Recallthat we defined03%By usingIn As we have arguedUi’s of value greaterguaranteeof a – ”—THEOREMof two half-spacesis precisely6; its intersectionwith the sphere is a sphericalO and, by symmetryof the sphere, thus has measureequal tostraightforwardly1, partperformance a” (1 – y).by usingthe change (i).guaranteeis establishedby thefollowinglemma.LEMMA3.5.PROOF.a .87856.Usingsimple9 2.331122.,thethe bound of 0.87856,calculus,nonzerowe firstone26—%-1for O 6 s 7r/2.impliesthat,The concavitycan see thata achievesroot of cos 6 (3 sin 6 1. Toobserve thatits valueformally 1COSOof ( ) 1 – cos 0 in the rangefor any O., we have (13) s (do)7r/2s(3 s n- ( – 00) ’( 6), or 1 – cos 9 s1 – cos 190 (0 – t90)sin /30 9 sin 190 (1 – cos 00 – 60sin 6.). 2.331122 for which 1 – cos 130– OOsin 00 0,we derive that0 sin O., implyingforproveChoosingf301 – cos O that2 0.87856.a T sin 130We have analyzed the expected value of the cut returnedby the algorithm.For randomizedalgorithms,one can often also give high probabilityresults. Inthis case, however, even computingthe variance of the cut value analyticallyisdifficult.Nevertheless,one could use the fact that W is bounded(by i. j Wij)to give lowerboundson the probabilitythatW is less than(1 – )E[W].

Algorithmsfor MaximumCut and SatisjiabilityProblems13.23tFIG. 1. (i) Plot of z arccos(y)\ as a function of t (1 – y). The ratio z/t is thus the slopeof the line between (O,O) and (z, t). The minimum slope is precisely a 0.742/0.844 andcorresponds to the dashed line. (ii) The plot also represents h(t) arccos(l – 2t)/ r as functi,on of t.As t approaches 1, h(t)/t also approaches 1. (iii) The dashed line corresponds to hbetween O and y .844.3.1 ANALYSIS WHEN THE MAXIMUMCUT Is LARGE.We can refinetheanalysis and prove a better performanceguaranteewheneverthe value of therelaxation(P) constitutesa large fractionof the total weight.DefineJJ& i.j wijandthe minimumh(t)of h(t)/t arccos(l-2t)/m.in the intervalLety be the value(O, 1]. The valueof t attainingof y is approximately.84458.THIEOREM 3.1.1.LetA IfA#-g,wijl-;tot1 J””j z y, thenThe theoremimplies a performanceguaranteeof h(A)/A– c when A y.As A varies betweeny and 1, one easily verifies that h(A)\xlvaries betweena and 1 (see Figure1, part (ii)).PROOF.can rewritefor e (i, j),LettingA, wij/ WtOt and x, (1 – Ui” Uj)/2A as A , A X,. The expected weight of the cut producedweby

M. X. GOEMANS AND D. P. WILLIAMSON1124the algorithmis equaltoarccos(larccos( Ui c vj )E[w] w[ji cj—.w& AJz(xe). Wtot AeeT– 2X, )‘i-reTo boundE[w],we evaluateMin A.h(x.)subjectto:;A xg AeO xeConsidertherel xationobtained l.by replacingh(t)by thelargestx (pointwise)convex functionk(t) smaller or equal to h(t). It is easy to see that h(t) is linearwith slope a between O and y, and then equal to h(t) for any t greater than y.See Figure1, part(iii). A#(.x.)But &fi(x,)we havefunction.Thisa k &xg()cewherefor A y,used the factthat e Z(A) h(A),eA, 1, A. 0 and that& is a convexshows thatE[w] wtot/z(z4) yp,wi,y’,Z Jproving the result.3.2 ANALYSIS FOR NEGATIVEEDGE WEIGHTS.So far, we have assumedthatthe weights are nonnegative.In several practicalproblems,some edge weightsare negative[Barahonaet al. 1988]. In this case the definitionof the performanceguaranteehas to be modifiedor t{E[W]since the optimuma correspondingW. – W.}xi.j Wij,valuegeneralizationcouldThe quantity i j:wij oI’vijE[w]z / ij(l– W.arccos( i “ Uj ) –ui.uj) – W.can be written i j:wi,3.3 towhere x- nzirz(O, x). Then)I\Li jPROOF.be positiveof Theoreml ,jl O (.asarccos(ui%-“ ‘j).)

AlgorithmsSimilarly,for Maximum(z Cut and Satisylabilityi j Wij(l– Ui “ Uj) – W )Problemsis equaltoI–vi”vj wij2 i j:wij OThe resultit.ElLEMMAtherefore3.2.2.PROOF.z i , j O1’’’’ijllfollowsForfollowsthatfrom3.4 andLemmam – arccos(z)3.3 A NEW FORMULATIONour analysis is a newConsiderthe followingLemmathe– 1 s z s 1, 1 – 1 arccos(z)/mThe lemma--y and notingfrom‘ Maximize wijAnvariationof a” (1 z).3.4 by usingCUT.formulationprogram:.followinga changeinterestingof theof variables arccos( –z).OF MAXnonlinearnonlinear“ ‘jconsequencemaximumcutofproblem.arccos( Ui “ vi) i jsubject(R)LetZj denoteto:the optimalT13E0REM 3.3.1.Z:value Z c.PROOF.We first show thatof (Q): the objectivefunctioncase of vectors.vi lyingZ: Z*MC. This follows since (R) is a relaxationof (R) reduces to xi j Wij (1 – Uivj) in thein a l-dimensionalTO see that z: Z&C 1A theFrom Theorem3.1, we see thatexpectedleastvalueof this program.is exactlyZ;,space.VeCtOrS Vi denote the optimalsolutionto ( ).the randomizedalgorithmgives a cut whoseimplyingthattheremustexista cut of valueat Z:.4. Relaxationsand DualityIn this section, we address the questionof solving the relaxation(P). We do soby showing that (P) is equivalentto a semidefiniteprogram,We then explorethe dual of this semidefiniteprogramand relate it to the eigenvalueminimization bound of Delormeand Poljak [1993a; 1993b].4.1 SOLVING THE RELAXATION.We beginby definingsome termsandnotation.All matricesunderconsiderationare definedover the reals. Ann x n matrixX%.X :20.TheA is said to be positivefollowingstatementssemidefiniteare equivalentif forforevery vectora symmetricx R”,matrixA(see, e.g., Lancasterand Tismenets@[19851); (i) A is positive semidefinite,(ii)all eigenvaluesof A are nonnegative,and (iii) there exists a matrix B such thatA J?TB. In (iii), B can either be a (possiblysingular)n X n matrix,or anpositive semidefinite matrixm X n matrix for some rrz n. Given a symmetricA, an m x n matrixB of full row-ranksatisfying (iii) can be obtainedin 0(rz3)time using an incompleteCholesky decomposition[Golub and Van Loan 1983,p. 90, P5.2-3].

1126M. X. GOEMANS AND D. P. WILLIAMSONUsing the decompositionY with y,, 1 correspondssimplycorrespondY BTB, one can see that a positive semidefinitepreciselyto a set of unit vectors UI, . . . . u. S :the vectorUi to the ithcolumnof B. Thenyij ZJi. Uj. Thematrix Y is known as the Gram matrix of {u,, ., u.} [Lancasterand Tismenetwe ;aireformulate(P)as athis equivalence;sky 1985, p. 110]. UsingsemidefiniteZ:program:; Max ,wij(lG ]– y j)(SD)subjectto :yii 1Y symmetricwhereY .inforanyusing 0,solutionsto(SD)et al. 1990]. e;thean algorithma nitereferredwe cannotZ;for anZ:toassolve (SD)–factbeone can intimepolynomialin the input size and log l/ .For example, Alizadeh’sadaptationofYe’s interior-pointalgorithmto semidefiniteprogramming[Alizadeh1995]performsture ofO(&(logWtOt log l/ ))iterations.By exploitingthe simple structhe problem(SD) as is indicatedin Rendlet al. [1993] (see alsoVandenberghein 0(n3) time.and Boyd [1996, Sect. 7.4]), each iterationOnce an almost optimalsolutionto (SD)an incompleteCholeskysomedecompositionto obtaincan be implementedis found, one can usevectorsu , .,u. E S form s n such thatAmongsolutionalloptimumof lowrank.solutionsGroneto (SD),onecanet al. [1990]showthat(SD) (i.e., which cannot be expressed as the strictfeasible solutions)has rank at most 1 whereshowtheexistenceany extremeconvexsolutioncombinationofaofof other1(1 1) n,2thatis,For related results, see Li and Tam [1994], Christensenand Vesterstr@m[1979],Loewy [1980], and Laurentand Poljak [1996]. This means that there exists aprimaloptimumsolutionY*to (SD)of rankless thanm,andthattheoptimumvectors u, of (P) can be embeddedin R! with m .This resultalso follows from a more generalstatementabout semidefiniteprogramsdueto Barvinok[1995] and implicitin Pataki[1994]: any extremesolutionof ak linearequalitieshas rank at most 1 wheresemidefiniteprogramwith1(1 1)/2 k.

Algorithmsfor MaximumCut and Satisjiability4.2 THE SEMIDEFINITEelegantdualitycussingDUAL.forof a semidefiniterewritethe objective(SD).programfunction– j ijyij.As mentionedsemidefinitethe dual of the programfunction 01theoryIn matrixsubjectto:1127in the introduction,programming.It is typicalturnto assumethatthe objectiveForthis— yij),functionW (wij)can be expressed as C ‘C; in other words, the weightfor some vectorsCi’s and -yi Ci. Ci llci112. Theweakduality s cj), whichbetweencanor even ascan be com e-andTrdenotesthesemidefinite,where diag( y ) denotes the diagonalmatrix whose ith diagonaldual has a simple interpretation.Since W diag(y)is positiveShowingwedis-description:W diag( y ) positivew(S, ) ( z 6s ci) . ( jtopurpose, ij(lthe objectivewhereis annowas . * .form,thereWeis symmetric.of (SD)nientlywrittenas WtOt – Tr(WY),trace.The dual of (SD) has a very simple(D)Problems(P)is neverand (D),entry is Yi. Thesemidefinite,itWij can be viewed as Ci Cjweightof any cut is thusgreaternamelythanthatZ: Z:,is easy.Considerany primalfeasiblesolutionY and any dual vector y. Since both Yand W diag( y) are positive semidefinite,we derive that Tr((diag( y) W)Y)z O l(see Lancasterand Tismenetsky[1985, p. 218, ex. 14]). But Tr((diag( y) W)Y) Tr(diag(y)Y)ference of the dualvalue is nonnegative.For semidefinitetheprimalvalue(respectively,and thereattained.programsoptimummaximummum) Tr(WY)objectiveThese,xiin theirminimum)yi Tr(WY),valuefullis equalis no guaranteehowever, functiontogenerality,theis in factthatimplyingand the primaldualtherethe supremumare pathologicalcases. functionis no guaranteeoptimuma s(SD)isand (D)behave nicely; both programsattain their optimumvalues, and these values areequal (i.e., Z; Z:).This can be shown in a variety of ways (see Poljak andRendl[1995a],Alizadeh[19951, and Barvinok[1995]).Given that strong dualityholds in our case, the argumentshowingweakduality implies that, for the optimumprimal solutionY* and the optimumdualsolutiony*, we have Tr((diag(y*) W) Y

symmetric matrix subject to linear equality constraints and the constraint that the matrix be positive semidefinite. Semidefinite programming is a special case of convex programming and also of the so-called linear programming over cones or cone-LP since the set of positive semidefinite matrices constitutes a convex cone.