DIMACSSeriesinDiscreteMathematicsandTheoreticalComputerScienceVolume00ComputingNear-OptimalSolutionstoCombinatorialOptimizationProblemsDAVIDB.SHMOYSMayAbstractInthepastfewyears,therehasbeensignicantprogressinourunderstandingoftheextenttowhichnear-optimalsolutionscanbee-cientlycomputedforNP-hardcombinatorialoptimizationproblems.Thispapersurveystheserecentdevelopments,whileconcentratingonthead-vancesmadeinthedesignandanalysisofapproximationalgorithms,andinparticular,onthoseresultsthatrelyonlinearprogramminganditsgen-eralizations.Inthepastfewyears,therehavebeenmajoradvancesinourunderstandingofperformanceguaranteesforapproximationalgorithmsforNP-hardcombina-torialoptimizationproblems.Mostnotablyaftertwenty-veyearsofessentiallynoprogress,anewtechniquehasbeendevelopedforprovingthatcertainap-proximationalgorithmsareunlikelytoexist.Partiallyinresponsetothisde-velopment,therehavealsobeensignicantrecentadvancesinthedesignandanalysisofapproximationalgorithms.Inthissurveywewilloutlineafewoftheareasinwhichprogresshasbeenmade,andsuggestdirectionsinwhichthereisstillinterestingworktobedone.Thecentraldenitionofthissurveyisthatofa-approximationalgorithmforanoptimizationproblem:apolynomial-timealgorithmthatdeliversafeasiblesolutionofobjectivefunctionvaluewithinafactorofofoptimal.ThestudyofapproximationalgorithmspredatesthetheoryofNP-completeness.Someearlyresults,suchastheproofduetoVizingthatagraphalwayshasMathematicsSubjectClassicationPrimary90C27,68Q25,05C85;Secondary68Q05,90C05.ResearchpartiallysupportedbyNSFgrantCCR-9307391,NSFPYIgrantCCR-8896272withmatchingsupportfromUPS,Sun,ProctorGamble,andDuPont,andbytheNa-tionalScienceFoundation,theAirForceOceofScienticResearch,andtheOceofNavalResearch,throughNSFgrantDMS-8920550cAmericanMathematicalSocietyperpage

DAVIDB.SHMOYSanedgecoloringwithatmostonemorecolorthanthemaximumdegree,werenotevenalgorithmicallystated,butstillcontainalloftheideasneededtogiveaninterestingapproximationalgorithm.Grahaminstudyingaparticu-larschedulingproblem,moreexplicitlystatedthegoalofanalyzinganecientheuristicfromtheperspectiveofitsworst-caseerrorbound,ormorepositivelystated,itsperformanceguarantee.TheseminalworkofJohnson(1974a,1974b),reactingtotherecentdiscoveryofthetheoryofNP-completeness,crystallizedtheperspectivethatoneapproachtocopingwiththeintractabilityofaproblemistodesignandanalyzeapproximationalgorithms.Johnson(1974a,1974b)consideredavarietyofproblemsthathavebecome,overtheinterveningyears,someofthecentralquestionsofthearea,includingthebin-packingproblem,maximumcliqueproblem,theminimumvertexcoloringproblem,themaximumsatisabilityproblem,andthesetcoveringproblem.Aswenowunderstandmuchmoreclearlytheseproblemsareallequivalent,inthattheyareNP-complete,andyetareverydierentintheextenttowhichgoodapproximationalgorithmsexistforthem.ItisilluminatingtoconsidertheconcludingquestionsposedbyJohnson(1974b):ArethereO(logncoloringalgorithms?ArethereanycliquendingalgorithmsbetterthanOnforallWhatisitthatmakesalgorithmsfordierentproblemsbehaveinthesameway?Istheresomestrongerkindofreducibilitythanthesimplepolynomialreducibilitythatwillexplaintheseresults...?Whileitmusthavebeennaturaltosuspectthatsomeofthesequestionswouldbehardtoanswer,itisunlikelythatthetruedicultyofeventheeasiestofthesequestionswassuspectedatthetime.Forexample,morethanadecadeelapsedbeforethe2-approximationalgorithmgivenforthegeneralmaximumsatisabilityproblemwasimproveduponatall.Thissurveyisnotintendedtobeacomprehensiveaccountoftheprogressofthosetwentyyears.Instead,wewillfocusonafewofthecentralissuesandproblems,andtrytooutlinesomeofthemainideasthathavebeenrecentlyintroduced.Inparticular,indescribingthealgorithmicadvances,wewilltrytoemphasizetheroleoflinearprogramminganditsgeneralizationsinthedesignandanalysisofapproximationalgorithms.ProbabilisticProofsandApproximationAlgorithmsOverthepastseveralyears,oneofthefundamentalthreadsofresearchincomputationalcomplexitytheoryhasbeentogiverandomizedcharacterizationsofdeterministiccomplexityclasses.Forexample,wenowknowthatPSPACEisexactlytheclassoflanguagesacceptedbyinteractiveproofsystemsandNEXPisexactlytheclassacceptedby2-proverinteractiveproofs.TheculminationofthislineofresearchwasanewandsurprisingcharacterizationofNPwhichwasinpartmotivatedbytherecentlydiscoveredconnectionbetweenhardnessof

COMPUTINGNEAR-OPTIMALSOLUTIONSapproximationresultsandrandomizedcharacterizations.Weshallnotattempttogiveacompletedescriptionofthedevelopmentofthisimportantlineofre-search,sincethishasbeenexcellentlysurveyedbyJohnsonHowever,inthissectionwewillgiveabriefoverviewofthisareaanditsconnectiontothecomplexityofcomputingnear-optimalsolutions.LetjxjdenotethelengthofastringxAlanguageLisinNPifthereisapolynomialpnandapolynomial-timeverifyingalgorithmVx;ythatsatisestwoconditions:ifxLthenthereisa(proofyforwhichjyjpjxjsuchthatVoutputs\yes";ifxLthenforevery(proofyforwhichjyjpjxjVoutputs\no".Moreinformallytheveriercanbeconvinced(bythecorrectproofthatxLinsuchawaythatheisneverfooled.ExtendingworkofAroraSafraArora,Lund,Motwani,Sudan,Szegedyprovedthatthefollowingisanequivalentdenition:theveriertossesrO(logjxjcoinstodeterminekObitpositionsilfpjxjgthen,byexaminingxandonlythosepositionsoftheprooftheverieranswers\yes"or\no"insuchawaythat:ifxLthenthereisa(proofyforwhichjyjpjxjsuchthatVoutputs\yes"foralloutcomesofthecointosses;ifxLthenforevery(proofyforwhichjyjpjxjVoutputs\no"formorethanhalfoftheoutcomesofthecointosses.SincethisverierisallowedtouseO(lognrandombits,andtoaccessOpositionsoftheproof,theclassoflanguagesrecognizedbysuchprobabilisticveriersisdenotedPCP(logn;Thus,thetheoremofArora,Lund,Motwani,Sudan,Szegedycanbestated:NPPCP(logn;Duetoitsspecialproperties,suchaproofthatxLhassometimesbeencalledaholographicproofFeige,Goldwasser,Lovasz,Safra,Szegedyobservedaninterestingconnectionbetweencomplexityclasscharacterizationsofthissortandapprox-imationalgorithms.TounderstandtheessenceofthisconnectionconsiderthefollowingoptimalproofproblemdenedbyaprobabilisticverierVforanNPcompletelanguageLforanyinputxnda\proofsoastomaximizethenumberofthercointossesthatleadtheveriertooutput\yes".IfxLthenforthecorrectproof,theverieracceptsforallofitsrcointosses.How-ever,ifxLthenforanyproof,fewerthanrcointossesleadtoacceptance.Hence,any2-approximationalgorithmfortheoptimalproofproblemcanbeusedtodecideifxLbymerelycheckingiftheprooffoundforinputxhasatleastrcointossesthatleadtoacceptance.Sincethischeckingcanbedoneinpolynomialtime,wehaveapolynomial-timealgorithmforLandhenceP=NPInotherwords,no2-approximationalgorithmexistsunlessP=NPOfcourse,theoptimizationproblemdenedaboveisnotaparticularlynaturalone.Itwouldbeniceifwecouldusethesamephilosophyforspeciccombi-natorialoptimizationproblems.Feigeetal.rstappliedthismethodtothemaximumcliqueproblemgivenagraphGVEndasubsetSofpairwiseadjacentverticessoastomaximizejSjInfact,someofthestrongesthardness-of-approximationresultshavebeensubsequentlyobtainedforthisproblem:there

DAVIDB.SHMOYSexistsansuchthatnojVj-approximationalgorithmexistsunlessP=NPWeshalldeferamoredetaileddiscussionofresultsforthisproblemuntilSectionForsomecombinatorialoptimizationproblems,itispossibletoecientlyndsolutionsthatarearbitrarilyclosetooptimal.Apolynomialapproxima-tionschemeforanoptimizationproblemisafamilyofalgorithmsAsuchthatforeachAisa-approximationalgorithm.However,formanyprob-lems,thereisnopolynomialapproximationschemeknown,anduntilrecentlynoevidencetosuggestthatnoneexists.Considerthemaximum3-satisabilityproblemMax3-Satgivenacollec-tionofclauses,eachofwhichistheorofatmostliterals,thatis,Booleanvariablesandtheirnegations,assignthevaluestrueorfalsetoeachofthenvariablessoastomaximizethenumberofclausesthataremadetruebythisassignment.AsacorollaryofthefactthatNPPCP(logn;Aroraetal.obtainedastrikingresultforthisproblem:theyshowedthatnopolynomialapproximationschemefortheMax3-SatproblemexistsunlessP=NPWenextoutlinethisresult,whichcanbeviewedasanencodingoftheunnat-uraloptimizationproblemdiscussedaboveasaMax3-Satproblem.ConsidertheprobabilisticverierforsomeNP-completelanguageLwewillshowthatthereisaconstantsuchthatforanyxwecanconstructinpolynomial-timeaMax3-Satinstancesatisfying:ifxLthenhasanassignmentsatisfyingallofitsclauses;andifxLthenanyassignmentdoesnotsatisfyafractionof'sclauses.Ifwecancomputesuchathenwecanprovethatforanyno-approximationalgorithmexists,unlessP=NPLetmdenotethenumberofclausesinIfxLthentheoptimumvalueismandtheapproximationalgorithmmustndanassignmentthatsatisesmorethanmclauses.However,ifxLthennosuchassignmentexists.Thisyieldsapolynomial-timealgorithmtodecideifxLandhenceP=NPWenextexplainhowtocomputeTheexpressionhasavariableziforeachbitiofasupposedholographicproofthatxLEachassignmenttoalloftheBooleanvariableszicanbeinterpretedasapotentialholographicproof:ziistrueifandonlyiftheithbitoftheproofisLetdenoteapossibleoutcomeforthercointosses.Werstconstructanexpressionthatissatisableexactlywhentheverieraccepts,giventhatistheoutcomeofthecointosses.Givenwecancompute(inpolynomialtime)thekbitsoftheholographicproofthattheverierwillexamine.Therearekpossiblevaluesforthesebits,andeacheithercausestheveriertoacceptorreject.Sincekisaconstant,wecancompute,inpolynomialtime,whichoftheseassignmentscausestheveriertoaccept.EachofacceptingassignmentscanbeencodedbyaBooleanexpressionthatistheandoftheappropriatekliterals:foreachbitioftheholographicproofexamined,includeziorzidependingonwhetherthebitisorrespectivelyWecanthenencodealloftheacceptingvaluesasaBooleanexpressionwhichistheor

COMPUTINGNEAR-OPTIMALSOLUTIONSofterms,onetermforeachsettingofthekbitsthatleadstheveriertoaccept.Thisexpressioncanbeconvertedtoa3-SATexpressionalbeitonewithKkclauses.However,sincekisaconstant,soisKTheMax3-SatinstanceistheandoftheexpressionsforallpossibleSincerO(lognthereapolynomialnumberofpossiblecointossesandsohasbeencomputedinpolynomialtime.Weshowthathastheclaimedproperties.ClearlyifxLtheneachexpressionismadetruebysettingthevariablesaccordingtotheholographicproofforxpropertyholds.IfxLthenforanypotentialholographicproof,morethanhalfofthepossiblevaluesforleadtheveriertoreject.Inotherwords,foranyassignmentofallBooleanvariableszimorethanhalfoftheBooleanexpressionsarenotmadetruebythisassignment.Ifisfalseatleastclauseisnotsatised,whichisa=Kfractionofitsclauses.Thus,foranyassignmentforBooleanvariablesziatleastaKfractionof'sclausesarefalseIfwesetKweseethatpropertyisalsosatised.Thisconstructionisquiteinecient:thevalueofforwhichonecanprovethatno-approximationalgorithmforMax3-Satexistsisextremelysmall.However,insubsequentworktherehasbeensubstantialprogressonimprovingthisconstant.Bellare,Goldwasser,Lund,Russellshowedthatforanyifthereexistsa-approximationalgorithm,thenP=NPMorerecentlyBellareSudanfurtherimprovedthisvaluetoWeshalldiscussthecomplementaryalgorithmicresultsforthisprobleminSectionAlthoughtheresultofAroraetal.fortheMax3-Satproblemisofgreatimportanceinandofitself,theconsequencesofthisworkaregreatlymagni-edinconjunctionwithearlierworkofPapadimitriouYannakakisPapadimitriouYannakakisobservedthatformanysimpleoptimizationprob-lems,thestateoftheartcircawasroughlythefollowing:virtuallyanynaivealgorithmdeliversasolutionofvaluewithinaconstant,mostoftenofoptimal;noalgorithmwithbetterperformanceguaranteeisknown;thereisnoknowncomplexity-theoreticevidencetosupportthesuppositionthatnopolynomialapproximationschemeexists.Amongtheproblemsexhibitingthisbehaviorwerethemaximum3-satisabilityproblem,theminimumvertexcoverproblem,andthemaximumcutproblem.InviewofthesuccessofthetheoryofNP-completeness,theysoughtananalogousnotionofcompleteness,whereprovingthatnopolynomialapproximationschemeexistsforonecompleteprob-lemimpliesthesameresultforeachcompleteproblem.NotonlydidtheyderivesuchatheorywhichtheycalledMAXSNP-completeness,buttheresultofAroraetal.completedtheagenda,sinceitprovedthatnopolynomialapproximationschemeexists(assumingPNPforaMAXSNP-completeproblem,themaxi-mum3-satisabilityproblem.Intheremainderofthissection,webrieysketchthemaincomponentsoftheframeworkproposedbyPapadimitriouYannakakisTherstelementisthenotionofreducibilityfromproblemtoherewewishtodeneanotion

DAVIDB.SHMOYSthatallowsustoconcludethatifdoesnothaveapolynomialapproximationscheme,thenneitherdoesAnL-reductionconsistsoftwopolynomial-timecomputablefunctions:fmapsaninstancexofintoaninstanceoffxofwhereasgmapsafeasiblesolutionsfortheinstancefxofintoafeasiblesolutiongsforxletOPTiIdenotetheoptimalvalueofiforagiveninputIwerequirethattherebeaconstantsuchthatOPT2fxOPT1xnallywerequirethattherebeaconstantsuchthattheabsolutevalueofthedeviationfromoptimalityofgsisatmosttimestheabsolutedeviationfromoptimalityofsWeshowthatifthereexistsapolynomialapproximationschemeforthentheremustbeoneforaswell.Equivalentlywewishtoshowthat,usingapolynomialapproximationschemeforwecanderive,foranyapolynomial-timealgorithmforwheretheabsolutedeviationfromoptimalityisatmostOPT1Givenaninputxwecomputefxapplyaapproximationalgorithmtothisinstanceoftogetafeasiblesolutionsandnallycomputegswhichistheoutput.Theabsolutedeviationfromoptimal-ityofsisatmostOPT2fxwhichisatmostOPT1xHence,theabsolutedeviationfromoptimalityofgsisatmostOPT1xIfwesetwehaveattainedthedesiredgoal.FollowingtheexpositioninPapadimitriouwerstdeneamorere-strictivecomplexityclass,MAXSNPAmaximizationproblemisintheclassMAXSNPifitcanbeformulatedasmaxSjfzzkVkGGGmS;zzkgjwheretheinputtoisasetofrelationsGGmoverVaniteuniverse,andisaquantier-freerst-orderexpressioninvolvingthevariableszitheinput,andanr-aryrelationSinwords,theoptimizationproblemistondtherelationthatmaximizesthenumberofassignmentsforzthatcausetohold.ThisdenitionwasmotivatedbythecharacterizationofNPbyFaginasalllanguagesthatcanbeformulatedinexistentialsecond-orderlogic.Toillustratethisdenition,considerthemaximumdirectedcutproblemgivenadirectedgraphGVAndasetSVsoastomaximizethenumberofedgesu;vwithuSbutvSTocastthisproblemintheformgivenabove,weletthevertexsetVbetheuniverse,letGu;vbethebinaryrelationoverVthatholdsexactlywhenu;vAandletSbeaunaryrelationoverVwewishtomaxSjfzzVGzzSzSzgjTocompletethedenitionofMAXSNPwesaythatanyoptimizationproblemisinMAXSNPifthereexistsaproblemMAXSNPsuchthatL-reducestoAproblemisMAXSNP-hardifeveryprobleminMAXSNPisL-reducibletoit.FinallyaproblemisMAXSNP-completeifitisinMAXSNPanditisMAXSNP-hard.

COMPUTINGNEAR-OPTIMALSOLUTIONSItisnothardtoshowthattheMax3-SatproblemisinMAXSNPandhenceinMAXSNPPapadimitriouYannakakisshowedthatitisalsocomplete.ThereisnowarespectablylonglistofproblemsknowntobeMAXSNPhard.Inadditiontotheproblemsmentionedabove,themaximumacyclicsub-graphproblem,thetravelingsalesmanproblem,themaximumcliqueproblem,theminimumSteinertreeproblem,andthemaximumsuperstringproblem(andinmanycases,veryrestrictivecasesofeach)areknowntobeMAXSNP-hard.ManyoftheseproblemswillbeaddressedindetaillaterinthissurveyRecentlyKhanna,Motwani,Sudan,Vazirani(unpublishedmanuscript)havearguedthatthisdenitionforMAXSNPisthemostnaturalone,sinceithasasacon-sequencethatMAXSNPisexactlytheclassofoptimizationproblemsthatareapproximablewithinsomeconstantfactor.Aprototypicalexample:thevertexcoverproblemInthissurveywewillemphasizetheroleoflinearprogramminginthedesignandanalysisofapproximationalgorithms.Inthissection,wewillstudyoneproblem,theweightedvertexcoverproblem,sinceitservesasagoodexampleformanyofthewaysinwhichlinearprogrammingarisesinthisarea.Theminimum-weightvertexcoverproblemisasfollows:wearegivenagraphGVEandaweightwvforeachvertexvVandwewishtoselectasubsetofverticesSVsuchthatuSorvSforeachedgeu;vEsoastominimizethetotalweightofSwSPvSwvPapadimitriouYannakakisshowedthatthevertexcoverproblemisMAXSNP-hard,evenifeachweightisandthedegreeofeachvertexisboundedbyaconstantkThefollowingisasimpleintegerprogrammingformulationoftheminimumweightvertexcoverproblem:minimizeXvVwvxvsubjecttoxuxvforeachu;vExvfgforeachvVLetOPTVCIdenotetheoptimalvalueforagiveninputIThereisaverysimple(toexplain)algorithmthatalwaysdeliversasolutionofweightatmostOPTVCIFirst,solvethelinearrelaxationofthisintegerprogram;i.e.,re-placeequationbyxvforeachvVLetxdenotetheoptimalsolutiontothislinearprogram.Next,constructan

DAVIDB.SHMOYSintegersolutionxbyroundingxinthemostnaturalway:foreachvVsetxvifxvotherwise.WeclaimthatxisafeasiblesolutiontotheintegerprogramofweightatmostXvVwvxvOPTVCIToseethatthissolutionisfeasible,observethattheconstraintforedgeu;vensuresthatatleastoneofxuandxvisatleasthence,atleastoneofxuandxvwillbesettoFurthermore,theroundinghasthepropertythatxvxvforeachvVandsoweobtainthefactthattheweightofthecovercorrespondingtoxisatmostOPTVCIThisalgorithmisthesimplestexampleofaroundingprocedurewendnear-optimalsolutionsforaparticularproblembygivinganintegerprogrammingformulation,solvingitslinearrelaxation,andthenapplyinganecientlycom-putableroundingproceduretoproducethedesiredintegersolution.Thisisaverysimpleresult,andinitssimplicitythisalgorithmignoressomeoftheinterestingunderlyingstructureoftheproblem.Whenwesolvethelinearrelaxationwewouldtypicallycomputeanextremepointofthefeasibleregion,andsuchextremepointssometimeshaveamuchsimplerstructurethatmighthelpindesigningtheroundingprocedure.Forthisproblem,itiswellknownthatanyextremepointxhasthepropertythatforeachvVxvfg(see,forexample,NemhauserTrotterBalinskiSpielbergandLorentzenUnfortunatelythisfactdoesnotimprovetheperformanceguaranteeofourroundingprocedure.Theadditionalstructuredoesimplicitlyhelpimprovetheeciencyofouralgorithm,sinceitisnothardtoshowthattheproblemofndingtheminimumfg-solutioncanbereducedtothemaximumowproblem;consequentlythelinearprogramcanbesolvedmuchmoreecientlythananarbitrarylinearprogram.Theconnectionbetweentheserelaxationsandapproximationalgorithmsfortheminimum-weightvertexcoverproblemwasrstobservedbyHochbaumwhogavetherst2-approximationalgorithmfortheproblem.Thelinearrelaxationcanalsobeexploitedinalessexplicitwaytodesignevenmoreecientalgorithms.Supposethatwedesignapolynomial-timealgorithmthatsimultaneouslyconstructsanintegerprimalsolutionandafeasiblesolutiontotheduallinearprogram.Sincethevalueofafeasibledualsolutiongivesalowerboundonboththeoptimallinearandintegerprimalsolutionvalues,ifwealsoknowthatthevalueoftheprimalintegersolutionisnomorethantimesthevalueofthedualsolution,thenthealgorithmisa-approximationalgorithm.Wewillcallsuchanalgorithmaprimal-dualalgorithm

COMPUTINGNEAR-OPTIMALSOLUTIONSCompletingourexampleofthevertexcoverproblem,weshallgiveasimpleprimal-dualalgorithm,whichisduetoBar-YehudaEvenTobegin,weformulatetheduallinearprogram:maximizeXeEyesubjecttoXevyewvforeachvVyeforeacheEwherevdenotesthesetofedgesfeEeu;vgForeaseofdiscussion,letaw-packingbeanassignmentofvaluestoedgessothatthetotalvalueoftheedgesincidenttovisatmostwvThedualisthentondaw-packingofmaximumtotalvalue.ItisinstructivetoconsiderthespecializationofthisproblemwhenwvforeachvVthatis,theunweightedcase.Ifwejustconsiderintegerdualsolutions,thenweseethattheconstraintsrestrictustofg-solutions,whichcorrespondtomatchings(i.e.,subsetsofedgessuchthatnotwoedgeshaveacommonendpoint).Aneasy2-approximationalgorithmfortheunweightedvertexcoverproblemisasfollows:ndamaximalmatchingMandoutputthevertexcoverSconsistingofallendpointsofedgesinM(NotethatMisonlyamaximalmatching,i.e.,foranyeEMMeisnotamatching.)ToseethatSisavertexcover,observethatifthereisanedgeewhichisnotcoveredbyoneofitsendpoints,thenecanbeaddedtoMtoformamatching,whichisacontradiction.Thematchingisafeasibledualsolution,andthesolutionSoutputisexactlyafactorofbiggerthanit.Hence,thisisa2-approximationalgorithm.Onedoesnotneedlinearprogrammingdualitytodeducethatthesizeofthematchingisalowerboundontheoptimumsizeofavertexcover:eachedgeinthematchingmustbecoveredbyadistinctvertex.Observethatwedidnotevenconstructtheoptimaldualsolution,eventhoughthatispossibleinpolynomialtime;theanalysisdidnotrequirethat.Infact,wereallywishtoconstructassmallamaximalmatchingaspossible.Consideragaintheweightedversion.Wewishtodesignanalgorithmanal-ogoustotheonediscussedaboveintheunweightedcase.CallanodevtightforagivenfeasibledualsolutionyifitscorrespondingconstraintissatisedwithequalityInitializethecoverSbeingconstructedtotheemptyset,thedualvariableyetoforeachedgeeEandrepeatthefollowingstepuntilalledgesofthegraphhavebeendeleted:chooseanyremainingedgeeu;vandincreaseitsvalueyeasmuchaspossiblewhilemaintainingthefeasibilityofthecurrentdualsolution(i.e.,untiltherstofitsendpointsbecomestight);addthetightnode(s)tothecoverSdeletethetightnode(s)andtheirincidentedges.

DAVIDB.SHMOYSTherearetwomainstepstoanalyzethisalgorithm:provingthatthesetconstructedisindeedavertexcover,andprovingthatitsweightisatmosttwicethevalueofthedualsolutionconstructed.ToshowthatSisavertexcoverattheendofthealgorithm,oneneedonlynotethatanedgeisonlydeletedwhenoneofitsendpointsistight,andhenceinthecover.SupposethatwheneveravariableyeisincreasedbykonepayskdollarstoeachoftheendpointsofeThus,thetotalamountpaidtothenodesofGisexactlytwicethevalueofthedualsolution.Observethatwheneveranodevisputinthecover,theremustbeexactlywvdollarspaidtoit,sincetheconstraintistight.Wecanthinkofthealgorithmasputtinganodevinthecoveronlywhenitspricewvistotallypaidfor.Hence,theweightofthenodesplacedinthecoverisatmostthetotalamountpaidtoallnodes,whichistwicethevalueofthedualsolution.Wehaveshownthattheprimal-dualalgorithmisa2-approximationalgorithm.Quitesurprisinglyforanyconstantno-approximationalgorithmisknown,evenifalloftheweightsareItremainsachallengingopenproblemtondsuchanalgorithm.RandomizedandDerandomizedRoundingThedenitionofthecomplexityclassMAXSNPwasmotivatedbytheover-whelminglackofprogressondesigningapproximationalgorithmsforahandfulofsimplecombinatorialoptimizationproblems,suchasthevertexcoverproblem.Forseveraloftheseproblems,themostnaivealgorithmsremainedtheoneswithbestknownperformanceguarantee.Fortunatelyforafewoftheseproblemstherehasbeensomeprogress,evensubstantialprogress,madeinthepastfewyears.Oneparadigmfordesigningalgorithmsthathasreceivedagreatdealofatten-tionrecentlyistodesignarandomizedalgorithmrst,andthen\derandomizeit"byinsomesense,simulatingtheroleoftherandomizationincriticalplacesinthealgorithm.AnearlyexampleofthisapproachisimplicitintheworkofJohnson(1974b)onthemaximum-weightsatisabilityproblemwhichisaweightedgeneralizationoftheproblemconsideredinSectiongivenacollec-tionofclauses,eachofwhichistheorof(anynumberofliterals,aswellasaweightwiforeachclauseCiassignthevaluestrueorfalsetoeachofthenvariablessoastomaximizethetotalweightoftheclausesthataremadetruebythisassignment.Firstconsiderthefollowingtrivialrandomizedalgorithmforthisproblem:foreachBooleanvariablevjindependentlysetvjtobetruewithprobabilityandsetittobefalsewithprobabilityBythelinearityofexpectation,theexpectedtotalweightoftheresultingassignmentisjustthesumoverallclausesoftheexpectedweightcontributedbyeachclause.ConsideraclauseCiandsupposethatithaskdistinctliterals.TherandomassignmentmakesthisclausetruewithprobabilityatleastkThus,theexpectedcontributionofthis

COMPUTINGNEAR-OPTIMALSOLUTIONSclausetotheweightoftheassignmentisatleastkwiConsequentlytheexpectedweightoftherandomassignmentforaninstanceinwhicheachclausehasatleastkliteralsisatleastkPiwiThisisclearlywithinafactorkofoptimal,sincetheoptimumisatmostPiwiSincekisatleastthisfactorisatmostWewilloutlineasimpleapproachtoobtainthesameperformanceguaranteedeterministicallyWhatwewishtocomputeisanassignmentoftotalweightthatisatleasttheexpectation.Thiscanbedonebythemethodofconditionalprob-abilitiesObservethatforanypartialassignmentofthevariables,onecaneasilycomputetheconditionalexpectationoftheweightoftheassignmentformedbycompletingthepartialonebyarandomassignmentchosenindependentlyanduniformlyThedeterministicalgorithmworksbyassigninganadditionalvariableineachiteration.Supposethatvvjarealreadyassigned.WecomputetheconditionalexpectationofthispartialassignmentrstwithvjalsosettofalseandthenagainwithitsettotrueIfwesetvjaccordingtowhichofthesevaluesisgreater,thentheconditionalexpectationattheendofiterationjisatleasttheconditionalexpectationattheendofiterationjThisimpliesthatthecompleteassignmentderivedhasweightatleasttheoriginal(unconditional)expectation.Thus,thisisa2-approximationalgorithm.Theanalysisdescribedabovealsoimpliesthatiftheinputdoesnotcon-tainanyclauseoflengththenthealgorithmndsanassignmentofweightwithinafactorofoftheoptimumYannakakisgaveanalgorithmthatessentiallyeliminatedallclausesoflengthinawaythatpreservestheperformanceguarantee,andtherebygavea4/3-approximationalgorithm.Goe-mansWilliamsonlatergaveamuchsimpleralgorithmwiththesameperformanceguarantee.Theiralgorithmisbasedontheideathattherandom-izedalgorithmmightperformbetterif,withalittlework,onecomputesforeachvariablevjamorerenedprobabilitychoicepjwithwhichtosetthatvariabletrueThemorerenedprobabilitiesarecomputedbysolvingthelinearrelaxationofanaturalfg-integerprogrammingformulationofthemaximum-weightsat-isabilityproblem.Weintroduceafg-variablexjforeachBooleanvariablevjandafg-variableziforeachclauseCiabinaryvariablesettocorre-spondstoaBooleanvariablesettotrueForeachclauseCiletTiindexthesetofBooleanvariablesthatoccurunnegatedinCiandletFiindexthesetofBooleanvariablesthatoccurnegatedinCiThen,wewishtoensurethataclausevariableziissettoonlyifoneoftheliteralsinthatclauseistrue:ziXjTixjXjFixjBylettingtheobjectivefunctionbetomaximizePiwiziweobtainanintegerprogrammingformulationofthisproblem.Letxzdenotetheoptimalsolu-tionforthelinearrelaxationofthisintegerprograminwhichallvariablesare

DAVIDB.SHMOYSinsteadboundedbetweenandIndependentlyseteachvariablevjtruewithprobabilitypjxjandfalsewithprobabilitypjRaghavanThompsonintroducedandanalyzedthisapproachofroundingafractionalsolutiontoafg-integersolutionbyinterpretingthefractionsasprobabilitiesandper-formingsucharandomizedroundingalbeitinthecontextofaVLSIroutingproblem.WecanviewwiziasthecontributionofclauseCitotheweightofthefrac-tionalassignment.AstraightforwardcomputationshowsthatifCihaskliterals,thentheexpectedcontributionofclauseCiintheassignmentfoundbyrandom-izedroundingisatleastkkwiziThisquantityisatleast=ewiziandhenceweexpecttoobtainasolutionofweightatleast=ePiwiziwherePiwiziisanupperboundontheoptimalweight.Applyingthemethodofconditionalprobabilities,weobtainane=e1)-approximationalgorithm.TomatchtheperformanceguaranteeoftheresultofYannakakisGoe-mansWilliamsonemployafrequentlyusedtechniqueinthedesignandanalysisofapproximationalgorithms:combinetwocomplementaryalgorithmswhichhavedisjointsetsofbadcases,byrunningbothandchoosingthebettersolution.Observethatthetworandomizedalgorithmsalreadydescribedappeartohavecomplementaryproperties:thelinearprogrammingapproachworksbestforshortclauses,whereastheuniformapproachworksbestforlongones.Morepreciselyifwersttossafaircointoselectwhichofthetwoalgorithmstorun,thentheexpectedcontributionofaclauseCiwithkliteralsisatleastk=kkwiziwiziThus,theexpectedvalueofatleastoneofthetworandomassignmentsisatleastoftheoptimalvalueoflinearprogrammingrelaxation.Thisimpliesthatifwerunbothalgorithmsandselectthebettersolution,thenweobtaina4/3-approximationalgorithm.GoemansWilliamsonalsoshowthata4/3-approximationalgorithmcanbeobtainedbyasingleroundingofthelinearprogrammingoptimalsolution;ratherthaninterpretingthefractionalsolutionasprobabilitiesdirectlytheyinsteadshowhowtomapfractionalsolutionstoprobabilitiesthat,whenusedforrandomizedrounding,areexpectedtoyieldgoodsolutions.Incontrast,thestrongestcurrentlyknownhardnessresult,duetoBellareSudanisthatapproximatingthisproblemwithinisNP-hard,evenifallweightsareLinearprogrammingrelaxationshaveplayedacentralroleinthedesignandanalysisofapproximationalgorithms.However,recentlytherehasbeenstrik-ingsuccessinbasingapproximationalgorithmsonmoregeneralmathematicalprogrammingtools,suchasconvexprogramming.Inthemaximum-weightcutproblemtheinputconsistsofann-vertexgraphGVEwhereeachedgeehasanassociatednonnegativeweightweandtheaimistondasetSVsoastomaximizethevalueofPeu;vuS;vSweThroughouttheremainder

COMPUTINGNEAR-OPTIMALSOLUTIONSofthissurveyweshallletSdenotethesetofedgesinthecutdenedbySfeu;vuS;vSgUntilrecentlythebestconstantperformanceguaranteeknownforthisprob-lemwasduetoSahniGonzalezTheiralgorithmcanalsobeviewedasaderandomizedrandomizedalgorithm.Inthiscase,therandomizedalgo-rithmis,foreachvertexvtoincludevSindependentlywithprobabilityTheexpectedvalueofthecutisthesumoveralledgeseu;voftheproductofitsweightweandtheprobabilitythatexactlyoneofuandvisinSSincethisprobabilityisexactlytheexpectedweightofthecutfoundisexactlyPeEweSincethetotalweightoftheedgesinthegraphisclearlyanupperboundontheoptimalvalue,theexpectationiswithinafactorofoftheweightofthemaximumcut.Byapplyingthemethodofconditionalprobabilities,weobtainthefollowingalgorithm:initerationjnwedecidewhetherornottoputvjScomputetheadditionalweightaddedtothecurrentcutifvjisaddedtoSornotaddedtoSandmakethedecisionforvjdependingonwhichisgreater.Onereformulationofthemaximum-weightcutproblemcanbestatedasfol-lows:foreachvertexvVassignitavaluexvfgtoindicatewhethervisinSornot;giventhisassignment,thecontributionofedgeeu;vtotheobjectivefunctioniswexuxvGoemansWilliamsongavearandomizedapproximationalgorithmforthemaximum-weightcutproblembasedonthefollowingrelaxation:foreachvertexvassignitann-dimensionalunit-lengthvectorxvsoastomaximizePeu;vEwexuxvwherexydenotestheinnerproductofxandyThealgorithmisquitesimple:ndanoptimalsolutionxtothisrelaxation,andselectann-dimensionalunit-lengthvectorruniformlyatrandom;putthoseverticesvinSforwhichxvrMoregeometricallywearebisectingthen-dimensionalunitspherebyahyperplanethroughtheorigin,andtherebyseparatingtheunit-lengthvectorscomputedbytherelaxationintotwosetsthatdetermineacut.Theanalysisofthisalgorithmisalsoremarkablysimple.LettheweightofthecutfoundbythealgorithmbetherandomvariableWWewishtoestimatethevalueoftheexpectationofWBylinearityofexpectation,thisisPeu;vEwePreSForeacheu;vwecancomputePreSbyobservingthatuandvenduponoppositesidesofthecutexactlywhentherandomhyperplanedenedbyrlies\inbetween"thevectorsxuandxvhencethisprobabilityisproportionaltotheangledenedbythesevectors,andisarccosxuxvAstraightforwardcalculationshowsthatforanyysuchthatyarccosyywheremincosHence,theexpectedweightofthecutfoundisatleastXeu;vEwexuxv

DAVIDB.SHMOYSInotherwords,theexpectedweightisatleastanfractionoftheoptimalvalueofthisnon-linearrelaxation,andhenceatleastanfractionoftheoptimalcutvalue.Itturnsoutthatisroughlyandsothisiswithinafactorofoftheoptimal.Tocomputeanoptimalsolutiontotherelaxation,wecanintroduceonevari-ableyu;vforeachinnerproductofunit-lengthvectorsxuxvItisnothardtoseethatyisofthisformexactlywhenthematrixYyu;vissymmetricpositivesemideniteandhasyvvforeachvVWewishtomaximizealinearobjectivefunctioninYsubjecttotheseconstraints.Thistypeofmathematicalprogrammingproblemisusuallyreferredtoasapositivesemideniteprogram,andcanbesolvedwithinanadditiveerrorofintimepolynomialinthesizeoftheinputandlog(1byforexample,theellipsoidalgorithm.Althoughthedetailsaremorecomplicated,thisalgorithmcanalsobederandomizedbythemethodofconditionalexpectations,andsothisyieldsa1.1393-approximationalgorithmfortheweightedmaximumcutproblem.SimilarrelaxationscanalsobeformulatedforthespecialcaseofthemaximumweightsatisabilityprobleminwhicheachclausehaslengthatmostPriortotheworkofGoemansWilliamsonnoapproximationalgorithmwithaperformanceguaranteesuperiortothatforthegeneralcasewasknown.Theyshowedthatthereisa1.1393-approximationalgorithmbasedonthisapproach.FeigeGoemans(privatecommunication)havefurtherstrengthenedtherelax-ationtogivea1.075-approximationalgorithm.Bothoftheseresultscanalsobeappliedtoyieldanincrementalimprovementontheperformanceguaranteeknownforthegeneralcaseofthisproblem.Onecuriousphenomenonshouldbenotedforeachoftheproblems(andtheirspecialcases)thatwehavestudiedthusfar.Thebestknownperformanceguar-anteefortheweightedcaseexactlymatchesthatfortheunweightedone.Itwouldbeinterestingtoknowifthereissomeunderlyingexplanationforthis.Centers,Tours,andSteinerTreesForsomeproblems,asimple-approximationalgorithmcanbeseentobebestpossible,inthesensethat,foranyno-approximationalgorithmexistsunlessP=NPOnesuchproblemistheminimump-centerproblem.TheinputconsistsofanintegerpandannnsymmetricdistancematrixCcijthatsatisesthetriangleinequality(i.e.,cijcjkcikforeachi;j;kwherecijspeciesthedistancebetweeneachpairofpointsi;jinfngforanyselectionSVofdesignatedcenters,theradiusofSistheminimumdistancersuchthateachpointiswithinrofsomepointinStheaimofthep-centerproblemistoselectasetSofsizepsoastominimizeitsradius.HochbaumShmoysgaveasimple2-approximationalgorithmforthep-centerproblem.Firstconsideradecisionversionoftheproblem,wherearadiusrisalsogiven,andyouwishtodecideifthereexistppointstoselect

COMPUTINGNEAR-OPTIMALSOLUTIONSofradiusrClearlybyperformingabisectionsearchovertheOnpossiblevaluesoftheoptimalvalue,onecanuseanalgorithmthatsolvesthedecisionproblemtondtheoptimalradius.Wegivearelaxedversionofsuchadecisionalgorithm,thateitheroutputscorrectlythatnosolutionofradiusrexists,orelsendsasetofppointsofradiusrByperformingabisectionsearchforanappropriatevalueofrsucharelaxeddecisionprocedureimmediatelyyieldsa2-approximationalgorithm.Adierent2-approximationalgorithmforthisproblemwasalsogivenbyDyerFriezeConsiderthefollowingalgorithm:repeatedlychooseoneoftheremainingpointsiadditoSanddeleteallpointswhosedistancefromiisatmostrAttheendofthisprocess,ifthesizeofthesetSexceedspoutputthatnosetofsizepandradiusrexists,andotherwiseoutputSItisclearthatifSisoutput,thenithasradiusatmostrsincethealgorithmwasdesignedsothatthismusthappen.WemustonlyshowthatifthereisasetSofsizeatmostpandradiusatmostrthenthealgorithmoutputsasetSofsizeatmostpSupposethereissuchasetSandassigneachpointtoitsclosestpointinSThus,wehavepartitionedthepointsintoatmostpparts,SSpThealgorithmcanselectatmostonepointifromeachpartSjsincetheselectionoficausesallremainingpointsinSjtobedeleted.Hence,atmostppointsareselectedbythealgorithm.HsuNemhauserobservedthatifthereexistsa-approximationalgorithmwiththenP=NPToseethis,considerthedominatingsetproblemwhichisNP-complete:givenagraphGVEandanintegerpdecideifthereexistsasetSVofsizepsuchthateachvertexiseitherinSoradjacenttoavertexinSGivenaninstanceofthedominatingsetproblem,wecandeneaninstanceofthep-centerproblembysettingthedistancebetweenadjacentverticestoandnon-adjacentverticestothereisdominatingsetofsizepifandonlyiftheoptimalradiusforthisp-centerinstanceisFurthermore,any-approximationalgorithmwithmustalwaysproduceasolutionofradiusifsuchasolutionexists,sinceanysolutionofradiusmustactuallybeofradiusForcombinatorialoptimizationproblemsdenedonadistancemetric,itisofinteresttoconsiderspecicmetrics,suchastheLLorLnorms,andaskwhethersuperiorperformanceinsuchaspecialcaseispossible.Foreachofthesecases,itisknownthatno-approximationalgorithmforthep-centerproblemexistsunlessP=NPforallwhereisaparticularvaluelessthanthatdependsonthemetric;forexample,fortheEuclideancase,pp(Mentzer(unpublishedmanuscript),FederGreeneHowever,fornoneofthesecasesisa-approximationalgorithmwithknown,andweconjecturethatsuchalgorithmsexist.Anaturalgeneralizationoftheproblemistorelaxtherestrictionthatthedistancematrixbesymmetric.Thisturnsouttobeanon-trivialgeneraliza-tion,andessentiallynothingisknownaboutperformanceguaranteesforthis

DAVIDB.SHMOYSextension.Intheremainderofthesection,wewilldiscusstwootheroptimizationprob-lemsdenedonpointsinagivendistancemetric:thetravelingsalesmanproblemandtheminimumSteinertreeproblem.Foreach,wewilldiscusstheknownre-sultsinthesymmetriccasewithtriangleinequalitydiscussimprovementsforspecialmetrics,andthenconsidertheasymmetriccase.InthetravelingsalesmanproblemTSPtheaimistondacyclicpermu-tationofthepointssoastominimizePniciiletOPTTSPCdenotetheoptimaltourlength.Rosenkrantz,Stearns,Lewisshowedthatthefollowingisa2-approximationalgorithm:maintainatourTonasubsetofthepoints,initiallyasinglepoint;iterativelyndthepointiTthatisclosesttosomepointjTandinsertiintoTafterjTheanalysisisbasedontheobservationthatthealgorithmusesasequenceofpairsi;jthatexactlymim-icsPrim'sminimumspanningtreealgorithm,anditisnothardtoshowthattheincreaseintourcostineachiterationisatmostcijSincetheoptimalvalueoftheminimumspanningtreeisatmostOPTTSPCthealgorithmisa2-approximationalgorithm.Christodesgavetheonlyknownimprovementtothisalgorithm.Firstconsiderthefollowingalternative2-approximationalgorithm:ndaminimumspanningtree,andtaketwocopiesofeachedgetoformanEuleriangraph;ndanEuleriantour,andordertheverticesastheyarerstencounteredonthistour.BythetriangleinequalitythecostofthecyclicpermutationfoundisnomorethanthetotalcostoftheEuleriangraph,whichisclearlyatmostOPTTSPCThis\double-tree"algorithmcanbeimprovedbyaugmentingaminimumspanningtreeTtoalessexpensiveEuleriangraph.Christodesobservedthataminimum-costperfectmatchingMontheverticesofodddegreeinThascostatmostOPTTSPCsinceanoptimaltouronthoseverticescanbepartitionedintotwoperfectmatchings.Hence,thecyclicpermutationcomputedfromanEuleriantouroftheunionofTandMhascostatmostOPTTSPCPapadimitriouYannakakisgavetherstevidencethatobtainingnear-optimalsolutionsfortheTSPishard,byshowingthattheTSPisMAXSNPhard,evenwhenrestrictedtosymmetricinstanceswitheachcijfgThere-fore,acorollaryoftheresultofArora,Lund,Motwani,Sudan,andSzegedyisthatnopolynomialapproximationschemefortheTSPwithtriangleinequalityexists,unlessP=NPOfcourse,thisdoesnotimplythatasimilarresultholdsforanyofthespecializedmetricsdiscussedabove:LLorLRemarkablynostrongerperformanceguaranteesareknownforthesespecialcases,noristhereevidencethatnopolynomialapproximationschemeexists.Itispossiblethatwesimplydonothavethetechnicaldexterityinmanipulat-ingL-reductionsthatwehaveacquiredforordinarypolynomial-timereductions.Ifthisistrue,onemightexpectthatcompletenessresultswillbeprovenforthesespecialmetrics.However,itwouldbeveryniceifitwerepossibletotake

COMPUTINGNEAR-OPTIMALSOLUTIONSadvantageoftheadditionalgeometricstructuresoastodesignapolynomialapproximationschemeforthesecases.TheasymmetricTSP(withtriangleinequality)appearstobesubstantiallyharderthanthesymmetriccase.Thebestknownalgorithm,duetoFrieze,Galbiati,Maoliworksbyndinganoptimalassignment(i.e.,ndapermutationthatminimizesPniciiwitheachciiifiscyclic,thenthissolutionisoutput;otherwise,onenodeisselectedfromeachcycle,andthealgorithmiscalledrecursivelyonthissubsetofnodes,whichisofsizeatmostn=Sincetheoptimalassignmentforanysubsetisnomorethanthecompleteoptimaltour,andthedepthofrecursionislognthisisalogn-approximationalgorithm.Itistemptingtoconjecturethatthisisasymptoticallyoptimal,buttheoptimistsamonguscontinuetohope(andtotrytoprove)otherwise.InconsideringthesymmetricTSPwhilenoapproximationalgorithmbetterthanChristodes'algorithmisknown,thereisreasontobelievethatbetteralgorithmsdoexist.IfweconsidertheinputtobethecompletegraphKnVEwhereeachedgeehascostcethenwecanformulatethefollowinglinearrelaxationoftheproblem:minimizeXeEcexesubjecttoXevxeforeachvVXeSxeforeachSVSxeforeacheEWolseyshowedthatthevalueofthislinearprogramisalwaysatleastoftheoptimumTSPvalue.AlternateproofsofthisfactaregivenbyGoemansBertsimasandShmoysWilliamsonThelatterisbasedonshowingthatChristodes'algorithmalwaysproducesatouroflengthwithinafactorofofthisrelaxation.IncontrasttoChristodes'algorithm,theanalysisoftheratiobetweenthislinearoptimumandtheintegeroptimumisnotknowntobetight.Infact,itiswidelyconjecturedthatthetrueworst-caseratioisMotivatedbythisexample,wedenea-estimationalgorithmtobeapoly-nomial-timealgorithmthatproducesavaluethatisatmosttheoptimalvalue,andisalwayswithinafactorofofit.Asopposedtoalgorithmsthatndoptimalsolutionsorvalues,thereisnoknown(polynomial-time)equivalencebetweenndingnear-optimalsolutionsandestimatingtheoptimalvaluewiththesameperformanceguarantee.Allknownnon-existenceresultsaboutapproximationalgorithmsareactuallyforthenon-existenceofanestimationalgorithm.Itwouldbeinterestingtoshow,forexamplefortheTSPthatthereisa-estimation

DAVIDB.SHMOYSalgorithm,andyetforsomeno-approximationalgorithmexistsunlessP=NPOralternativelyitwouldberemarkabletondakindofself-reducibilitythatallowsustoshowthatthetwotypesofguaranteesareequivalent.IntheminimumSteinertreeproblem,wearegivenasubsetofterminalsTValongwithametricdeningthedistancebetweenanytwopointsinVTheobjectiveistochooseaconnectedsubgraphthatspanstheterminalsofminimumtotalcost.ThesetVneednotbenite,suchasintheEuclideancasewhereVistheentireEuclideanplane.Thereisasimple2-approximationalgorithmknownforanarbitrarymetric.ComputeaminimumspanningtreeonthecompletegraphGTdenedbytheterminalsetTthatis,donotusetheSteinerpointsVTatall.Toseethatthisisa2-approximationalgorithm,weboundthelengthoftheminimumspanningtreeinGTbyshowingthatGThasaconnectedspanningsubgraphoflengthatmostthetwicethecostoftheoptimalSteinertree.Infact,weconstructaTSP-liketourofthiscost:weconverttheoptimalSteinertreeintoatourofitsterminalsbyusinga\double-tree"traversal.Zelikovskyprovidedthebreakthroughthatshowedhowtomakenon-trivialuseofSteinerpointsindesigninganapproximationalgorithmwithabetterperformanceguarantee.Takeanythreeterminalsu;vwTandcom-parethelengthoftheminimumspanningtreeonGTtothesumofthelengthoftheminimumSteinertreeconnectingjustuvandwandthelengthoftheminimumspanningtreeonceuvandwhavebeencontractedtoonepoint.Iftheformerislarger,thenclearlywecanconstructabetterSteinertreebycombiningthe3-terminalSteinertreewiththeminimumspanningtreeforthesmallerproblem.Thedierencebetweenthesetwovaluesiscalledthegainoffu;vwgZelikovsky'salgorithmrepeatedlycontractstriplesofterminals,choosingthetriplewiththegreatestgain,untilnotriplewithpositivegainex-ists.TheresultingSteinertreeisconstructedfromtheminimumspanningtreeontheremainingterminals,combinedwiththeSteinertreesassociatedwitheachcontractionalongthewayTheanalysisofthealgorithmconsistsoftwoparts:thatanoptimalsequenceofcontractionsyieldsaSteinertreeofvaluewithinafactorofoftheoptimalSteinertreelength;andthesequenceofcontractionsfoundbythisgreedyapproachhasatotalgainthatisatleasthalfoftheoptimaltotalgain.Consequentlythisalgorithmisan11/6-approximationalgorithm.ForZelikovsky'salgorithmtoruninpolynomialtime,itisnecessarytocom-puteaminimumSteinertreeonpointsinpolynomialtimeinthegivenmetric.Whiletherearemetricsforwhichthisisnotpossible,foreachofthemetricsgivenabove,oranysettingforwhichVisnite,thiscomputationcanbedoneinpolynomialtime.BermanRamaiyerextendZelikovsky'sscheme,incorporatingoptimalSteinertreesonmorepointstoyieldimprovedperfor-manceguarantees.Forexample,byusing4-tuplesitispossibletoderivea9-approximationalgorithm.InoneoftheearliestpapersoncomputationalaspectsoftheminimumSteiner

COMPUTINGNEAR-OPTIMALSOLUTIONStreeproblem,GilbertPollakconjecturedthattheminimumspanningtreewasalwaysoflengthwithinafactorofpofthelengthoftheoptimalSteinertree,wheneverthemetricisgivenbypointsintheEuclideanplane.DuHwangrecentlyprovedthisconjecture.Hwangshowedthatforrectilineardistancesintheplane,thisratioisalwaysatmostWhenana-lyzedintheserestrictedmetrics,Zelikovsky'salgorithmcanbeshowntoimproveonknownresultsinbothcases.Du,Zhang,Fengshowedthatthisalgo-rithmisa-approximationalgorithmwithpforEuclideancase,butdidnotgiveanexplicitvalueforZelikovskyandBermanRamaiyerinde-pendentlyshowedthatitisan8-approximationalgorithmfortherectilinearcase.Thelatterpaperalsogeneralizedthealgorithmtogetimprovedbounds;forexample,againusing4-tuplesyieldsa97/72-approximationalgorithm.BernPlassmanshowedthattheSteinertreeproblemisMAXSNPhardinthemetricinwhicheachdistanceiseitherorAsfortheTSPthisstillleavesopenthequestionaboutwhetherthereexistsapolynomialapproximationschemeforthegeometricallydenedmetrics.TodeneanasymmetricSteinertreeproblem,onecanconsiderthesettinginwhichtherealsoisaspeciedrootterminal,andyouwishtondabranchinginwhicheachterminalisreachablefromtheroot.Itisnothardtoshowthatthereisasimpleapproximationpreservingreductionfromthesetcoveringproblem,andhenceapolynomial-timealgorithmwithperformanceguaranteeo(lognisnotlikelytoexist(seeSectionNastygapsTheconnectionbetweenprobabilisticproofsandhardnessresultsforapprox-imationquestionshasgreatlyaidedourunderstandingoftheextenttowhichnear-optimalsolutionscanbeobtainedforcertaincombinatorialoptimizationproblems.However,therearemanyotherproblemsforwhichthisapproachdoesnotyetseemtoberelevant.Ofparticularinterestarethoseproblemsforwhichthereisaconstant-approximationalgorithmknown,andforsomeitispossibletoprovebyelementarymethodsthatno-approximationalgorithmexistsunlessP=NPInthissection,wewilldiscussafewexamplesofthiskind.Intheproblemofschedulingidenticalparallelmachinessubjecttoprecedenceconstraintswearegivenacollectionofjobsfngandmmachines,wherejobjhasaprocessingrequirementofpjtimeunits,andthereisapartialorderonthejobs,wherejkrequiresthatjobjcompleteitsprocessingbythetimejobkstarts.Eachjobmustbeassignedtoonemachinetobeprocessedwithoutinterruptionforitsspeciedamountoftime.Eachmachinecanbeassignedatmostonejobatatime.Theaimistondascheduleforalljobssoastominimizethemaximumjobcompletiontime.Oneoftheearliestresultsonapproximationalgorithmsdealswiththismodel.Grahamshowedthatthefollowingisa2-approximationalgorithm:the

DAVIDB.SHMOYSjobsarelistedinanyorderthatisconsistentwiththeprecedenceconstraints,andwheneveramachinebecomesidle,thenextjobonthelistwithallofitspredecessorscompletedisassignedtothatmachine;ifnosuchjobexists,thenthemachineisleftidleuntilthenextmachinecompletesajob.LetOPTMSIdenotetheoptimalvalueforaninstanceIToshowthatthescheduleproducedisnomorethantwicetheoptimallength,wewillpartitionthescheduleintotwoclassesoftimeintervals;foreach,itwillbeeasytoseethatitstotallengthisatmostOPTMSIConstructachainC(backwards)inthepartialorderasfollows:startwiththejobthatnisheslastintheschedule,selectitspredecessorinthatnisheslast,anditeratethisprocessuntilthenewjobidentieddoesnothaveanypredecessorsinConsiderthetimeduringwhichajobinCisbeingprocessed.SinceCisachain,thetotallengthoftheseintervalsisatmostOPTMSIHowever,atanyothertime,nomachineisidle,sincethenextjobinthechainisalreadyavailabletobeprocessed,allofitspredecessorshavingbeencompleted.SincethetotaltimeinwhichnomachineisidleisatmostOPTMSIthiscompletestheanalysis.LenstraRinnooyKanshowedthat,evenifeachjobjhasprocessingrequirementpjjndecidingifthereisascheduleoflengthisNP-complete.Thisimpliesthatforanyno-approximationalgorithmexistsunlessP=NPHowever,decidingifthereisascheduleoflengthisquiteeasyandhencenostrongerboundcanbeprovedviathisapproach.ItwouldbeaconsiderableadvanceinthetheoryofusingprobabilisticproofstoprovehardnessresultsforapproximationproblemsifitcouldbeusedtoimproveuponthelowerboundofAnotherexampleofaproblemwitha\nastygap"isthefollowingproblemofschedulingunrelatedparallelmachinesifjobjisassignedtomachineithenitrequirespijunitsofprocessingtime;eachjobmustbeassignedtoexactlyonemachine;thecompletiontimeofamachineisthetotalprocessingtimeofthejobsassignedtoit.Wewishtondanassignmentthatminimizesthemaximumcompletiontimeofanymachine;weshallcallthisthelengthoftheassignment.ThebestknownapproximationalgorithmforthisproblemisduetoLenstra,Shmoys,Tardoswhichreliesonadeterministicroundingapproachtondsolutionswithinafactoroftwoofoptimal.WecanformulatetheproblemofdecidingifthereexistsanassignmentoflengthatmostTasthefollowingintegerprogram:nXjpijxijTforeachim;mXixijforeachjn;xijfgforeachim;jn:

COMPUTINGNEAR-OPTIMALSOLUTIONSToobtainalinearrelaxation,replacetheconstraintbyxijifpijTxijforeachim;jn:Ifthelinearrelaxationdoesnothaveafeasiblesolution,thenclearlynointegersolutionexists.Otherwise,ndanextremepointxPottsobservedthatthissolutionhasatmostmnnon-zeroes,andhenceatmostmofthejobsarescheduledfractionallyHeusedthisobservation,foraweakerlinearrelaxation,toobtaina2-approximationalgorithmifthenumberofmachinesisaconstant.Lenstra,ShmoysTardosshowedthatxcanberoundedtoagoodassignment.Intuitivelywewouldliketodothissothateachmachineisassignedatmostoneofthefractionallyscheduledjobs;sinceximpliesthatpijTthisensuresthatthelengthoftheroundedassignmentisatmostTThislinearprogramisageneralizedowproblem,andwell-knownpropertiesofextremepointsforthegeneralizedowproblemcanbeusedtoshowthatsuchamatchingoffractionallyassignedjobsandmachinesmustexist.Furthermore,thematchingcanbefoundbyasimpleprocedurethatrunsinOmntime.Thisprocedurecanbeconvertedintoa2-approximationalgorithmfortheoptimizationversionoftheproblem,byperformingabisectionsearchfortheminimumTsuchthatthelinearrelaxationhasafeasiblesolution.Lenstra,Shmoys,TardosalsoprovedthatforanynoapproximationalgorithmexistsunlessP=NPInfact,thehardnessresultholdsif,foreachjobjitsprocessingtimeonanymachineiseitherpjorItwouldbenicetoshowthat,perhapsstartingwiththisspecialcase,thattherearealgorithmswithamatchingperformanceguarantee.Asfortheproblemofschedulingonidenticalparallelmachinessubjecttoprecedenceconstraints,itseemsdiculttoimprovethelowerboundbasedonthenewrandomizedcharacterizationofNPWeconcludethissectionwithotherdeterministicroundingresults,foragen-eralizationoftheproblemofschedulingunrelatedparallelmachines.Inthegeneralizedassignmentproblemwhenjobjisassignedtomachineiitnotonlyaddspijtotheloadonthismachine,butitincursacostcijaswell.NowwewishtodecideifthereisanassignmentoflengthTandtotalcostCSimilarroundingproceduresforthisproblemweregivenindependentlybyTrickandLinVitterWeshalloutlinetheresultofLinVitterwhichshowshowtocompute,foranyanassignmentoftotalcostCandlengthTassumingthatoneoftotalcostCandlengthTexists.TheintegerprogrammingformulationconsistsoftheconstraintsplusmXinXjcijxijC

DAVIDB.SHMOYSWerstcheckifthelinearrelaxationwhereconstraintsarereplacedbyandhasafeasiblesolution.Ifnot,thennoassignmentofcostatmostCandlengthatmostTexists.Otherwise,letxdenoteafeasiblesolution.Inthisfractionalassignment,eachjobjincursacostcjPmicijxijjnLetCdenotethesetofpairsi;jsuchthatcijcjletwjPi;j62Cxijthefractionofjobjthatisassignedrelativelycheaplyinthefractionalassignment.NotethatwjConsideranewfractionalassignmentxwherexijxij=wjifi;jCifi;jCSincewehavejustzeroedoutsomecomponentsofxandrescaled,xclearlysatisesFurthermore,sincewjforeachjnnXjpijxijTforeachim:ApplyingtheroundingtheoremofLenstra,Shmoys,TardostoxwegetasolutionoftotalcostatmostPnjcjCandlengthatmostTLinVitteralsogiveseveralotherapplicationsofthistypeofroundingtechnique,whichtheycallltering.ShmoysTardosgiveanimprovedroundingtechniquethatroundsanyfeasiblesolutioninpolynomialtimetoanassignmentofcostatmostCandlengthatmostTTheroundingisdonebyndingaminimum-costmatchinginanassociatedbipartitegraph.ThegraphisconstructedsoastoguaranteethatanymatchinghasthepropertythattheassociatedassignmenthaslengthatmostTfurthermore,thecostofthematchingisequaltothetotalcostoftheassignment.TheexistenceofagoodroundingisprovedbyexhibitingafractionalmatchingofcostCThus,bythetheoremofBirkhoandVonNeumanntheremustalsoexistanintegermatchingofcostatmostCThefractionalmatchingiseasilyderivedfromthefeasiblesolutiontothelinearrelaxation.Primal-dualalgorithmsfornetworkdesignproblemsApproximationalgorithmsareoftenbasedonlinearprogrammingbydesign-ingaprimal-dualapproximationalgorithm:thatis,wesimultaneouslyconstructanintegerprimalsolutionandadualsolutionsothattheirvaluesareprovablyclosetoeachother.InSectionwegaveanexampleofhowsuchanapproachcanbeusedforthevertexcoverproblem.Inthatcase,theprimarymotivationwastoimprovetheeciencyoftheapproximationalgorithm.However,inmanycasesthemosteectiveapproximationalgorithmsarebasedonthisapproach.Primal-dualalgorithmshavebeenparticularlysuccessfulfornetworkdesignproblems.Intheminimum-costsurvivablenetworkdesignproblemwearegivenanundirectedgraphGVEwhereeachedgeeEhasagivencostce

COMPUTINGNEAR-OPTIMALSOLUTIONSandforeachpairofnodesuandvthereisaspeciedconnectivityrequirementru;vtheaimistondaminimum-costsubgraphGVEsuchthatthereareru;vedge-disjointpathsbetweeneachpairu;vVThisproblemisacommongeneralizationofanumberofcombinatorialopti-mizationproblems.Formanyofthese,therequirementsaredenedimplicitlybynode-connectivityrequirements:foreachvVthereisavaluervandru;vminfrurvgForexample,ifrvforeachvVthenwemerelyrequireaminimum-costconnectedsubgraph;inotherwords,thisistheminimumspanningtreeproblem.MoregenerallyifrvkforeachvVthenwearelookingfortheminimumk-edge-connectednetwork.IfeachrvfgthenthisistheminimumSteinertreeproblem;anodevwithrvisater-minal,whereasonewithrvisaSteinernode.Therehasbeenagreatdealofresearchontheseandotherspecialcases,andweshallnotattempttosurveythisliterature.Weshallfocusinsteadonresultsfromoneparticularthreadofresearchthathasattemptedtouseanaturallinearprogrammingrelaxationtoobtaingoodperformanceguaranteesfortheseproblems.GoemansandBertsimasconsiderthefollowinglinearrelaxationofthesurvivablenetworkdesignprobleminthecasewhenru;vminfrurvgminimizeXeEcexesubjecttoXeSxemaxu;vSru;vforeachSVSxeforeacheETheirmainresultistoshowastrongstructuralpropertyofthislinearprogramwhenevertheedgecostssatisfythetriangleinequality:cu;vcvwcu;wforeachu;vwVThepropertyiscalledtheparsimoniouspropertyanditisasfollows:foranysubsetofnodesDifweaddtheconstraintsXeuxemaxvVuru;vforeachuDthentheoptimalvalueisunchanged.TheparsimoniouspropertycanbeusedtoshowthattheratiobetweenthecostoftheSteinertreeproducedbytheminimumspanningtreeheuristicandthelinearprogrammingrelaxationislessthanGoemansBertsimasalsoconsiderthevariantofthesurvivablenet-workdesignprobleminwhichthenetworkconstructedmaycontainmultiplecopiesofeachedge.TheygiveanaturalextensionoftheSteinertreeheuris-ticforthecasewhentheconnectivityrequirementsareoftheformru;vminfrurvgLetrmaxdenotethevaluemaxu;vVru;vThealgorithmworksinrmaxphases,whereinphaseirmaxthealgorithmaugments

DAVIDB.SHMOYStheconnectivityonthesubsetofnodesVifvVrvigbyrunningtheSteinertreeheuristicwiththesetofterminalsgivenbyViTheyprovethatiftherearekdistinctvaluesrvvVthenthisisaminfkHrmaxgapproximationalgorithmwhereHk=kistheharmonicfunction.Theideaofusingaprimal-dualapproachinthiscontextwasintroducedbyAgrawal,Klein,andRaviwhogavealogrmax-approximationalgorithmforthesameproblem,butwheretheconnectivityrequirementsneednotbeoftherestrictedform.Thealgorithmusesscalingtechniquestosatisfyonebitoftheconnectivityrequirementsatatime.Thecoreofthealgorithmisaapproximationalgorithmfortheproblemwitheachru;vfgwhichcanbeviewedasaSteinerforestproblemtherearesetsofterminalsTTTpandwewishtondtheminimum-costforestsuchthateachsetTjiscontainedinsomeconnectedcomponentoftheforest.GoemansWilliamsongiveaveryelegantgeneralizationthatexplic-itlyreliesonalinearprogrammingformulationtogiveaprimal-dualalgorithmthatisinmuchthesamespiritasprimal-dualalgorithmsforpolynomiallysolv-ablecombinatorialoptimizationproblems,suchastheminimum-costperfectmatchingproblem.TheyconsiderproblemsspeciedbytheintegerprogramminimizeXeEcexesubjecttoXeSxefSforeachSVSxefgforeacheEforabroadclassoffg-functionsfwhichtheycallproperfunctionsAproperfunctionmustsatisfytwoproperties:fSfVSforeachSVandifAandBaredisjoint,thenfABmaxffAfBgInadditiontothefg-problemsdiscussedabove,thisframeworkalsocaptures,forexample,thestshortestpathproblemandminimumT-joinproblem.Inordertoexplainthisalgorithm,werstformulatethedualofitslinearprogrammingrelaxation:maximizeXSVfSySsubjecttoXSeSySceforeacheEySforeachSVS

COMPUTINGNEAR-OPTIMALSOLUTIONSTheprimal-dualalgorithmmaintainsthefollowinginvariant:thereisapartitionofthenodesetCsuchthatthecurrentprimalsolutionisaforestwithcom-ponentsgivenbyCTheinitialprimalsolutionistheemptyset,sothateachpartinCisinitiallyjustasinglevertex.Afeasibledualsolutionismaintainedthroughout;initiallyeachySEachiterationofthealgorithmselectsoneedgeu;vthatconnectstwodistinctcomponents,andthenmergesthetwocomponents.TheedgeisselectedinthefollowingwayEachcomponentCofCforwhichfCisconsideredactivethatis,thecurrentprimalsolutionisinfeasiblewithrespecttoCToselectthenewedgetobeadded,wesetyCyCforeachactivecomponentCwhereissettobethelargestvaluethatmaintainsdualfeasibilityConsequentlythischangecausesoneoftheconstraintstobesatisedwithequalityThistightconstraintdeterminesthenewedgetobeaddedtotheprimalsolution.Whentherearenoactivecom-ponents,weconsidereachedgethathasbeenincludedinthesolutioninreverseorder,anddiscardeachthatisnotnecessaryfortheremainingsolutiontobefeasible.Someintuitionbehindthisclean-upphasecanbegainedbyconsideringthealgorithminthecasethatitiscomputingashorteststpath:thealgo-rithmgrowssingle-sourceshortest-pathtreesfromsandtuntilthetwotreesmeet;theneachedgewhichisnotonthisstpathisdeleted.Anotherapplicationofthisresultistoobtainafasterapproximationalgo-rithmfortheminimum-costperfectmatchingproblemforcoststhatsatisfythetriangleinequalityAlthoughthismatchingproblemcanbesolvedinpolynomialtime,thebestknownalgorithmforitrunsinOntimeondensegraphs.Incon-trast,thealgorithmpresentedabovecanbeimplementedtoruninOnlogntimeondensegraphs.Tocapturethematchingproblem,considerfSwhichisdenedtobeifjSjiseven,andifjSjisodd.Theresultingprimalsolutionwillnotnecessarilybeamatching;thealgorithmndsaforestinwhicheachcomponenthasanevennumberofnodes.However,eachcomponentcanbecon-vertedintoamatchingofnogreatercostbyconsideringthetourofthesenodesfoundbyshortcuttinga\double-tree"traversal,andthen,asintheanalysisofChristodes'algorithm,choosingthecheaperofthetwomatchingsformedbytakingalternateedgesinthetour.GoemansWilliamsonalsoapplytheirresulttothenetworkdesignproblemgivenbyanyproperfunction,whereeachedgemaybeincludedanynumberoftimes;thisyieldsaHrmax)-approximationalgorithminthissetting.AggarwalGargshowhowtoobtainaperformanceguaranteeofHkwherekdenotesthenumberofnodesvforwhichfvispositive.Althoughwehaveseenquiteanumberofresultsforthesurvivablenetworkdesignproblemwhenmultiplecopiesofeachmaybeincluded,thisproblemhasfewerapplicationsthanthevariantinwhicheachedgecanbeincludedatmostonce.Itappearstobemuchhardertoobtaingoodresultsforthisvariant,andweshallnowfocusondescribingtheresultsknownforit.TherststepwasduetoKleinRaviwhogavea3-approximationalgorithmforthenetwork

DAVIDB.SHMOYSdesignproblemforallproperfunctionswithrangefgWilliamson,Goemans,Mihail,andVaziranigavetherstapproxima-tionalgorithmforarbitraryproperfunctions.Theiralgorithmincrementallybuildsafeasiblesolutionbyaddingedgesinaseriesofrmaxphases,whereeachphaseisoneexecutionofthefg-algorithmdescribedabove.AcutSisde-cientifthenumberofedgesofSthatareinthecurrentsolutionislessthantherequirementforthatcut,fSIneachphase,wetargetthedecientcutsbyformulatingafg-problemgivenbyafunctionhSwhichisexactlywhenSisdecient.Thefg-algorithmdeliversasolutionthatiswithinafactorofoftheoveralloptimumandsothealgorithmisarmax-approximationalgorithm.Unfortunatelyhneednotbeaproperfunction,butitcanbeshowntobeanuncrossablefunction,forwhichWilliamsonetal.alsogivea2-approximationalgorithm.Inseveralparticularcases,thealgorithmcanbeshowntohaveastrongerperformanceguarantee;forexample,iffSfgforallSthenitisa3-approximationalgorithm.Gabow,Goemans,andWilliamsongiveamoreecientimplementationofthisapproach.ItturnsoutthatthealgorithmofWilliamsonetal.canbeimprovedinarathersimplewayLetthedeciencyofacutSbethenumberedgesofSthatmuststillbeaddedtothecurrentsolutiontobringthenumberofedgestobeatleastfSLetbethemaximumdeciencyofacut.Goemans,Goldberg,Plotkin,Shmoys,Tardos,andWilliamsonproposethatineachphase,onlythecutswithdeciencybetargeted;thatis,hSissettoforonlythosecuts.Byarguingthattheoptimumvalueforthisfg-problemisatmosttheoveralloptimumdividedbytheyshowthatthisyieldsaHrmaxapproximationalgorithm.Itremainsaninterestingquestionwhetherthereex-istsanapproximationalgorithmwithaconstantperformanceguaranteeforthisproblem.KhullerVishkingiveasimple2-approximationalgorithmforthecaseinwhichrvkforeachvV(thatis,theminimum-costk-connectedsubgraph).Theideaofthealgorithmisquitesimple;replaceeachundirectededgeu;vbytwodirectededges,u;vandvueachofcostequaltothecostoftheundirectededge.Chooseanarbitraryrootnodevandndkdisjointbranchingsintovofminimumtotalcost,aswellasaminimum-costfamilyofkdisjointbranchingsoutofvIncludean(undirected)edgeinthesolutionifeitherdirectedcopyisusedineithersolution.Itisnothardtoseethatthisisafeasiblesolution,andsincethecostofeitherfamilyofbranchingsisalowerboundontheoptimum,thisisa2-approximationalgorithm.AnaturalrststeptowardsaconstantperformanceguaranteeforthenetworkdesignproblemspeciedbyproperfunctionswouldbetoconsidertheSteinerversionofthek-connectedsubgraphproblem,thatis,rvfkgforeachvVHochbaumNaor(unpublishedmanuscript)consideranotherspecialcase,inwhichtheproperfunctionfShasthepropertythatjSjpfSandgiveanO(logp)-approximationalgorithmforthiscase.

COMPUTINGNEAR-OPTIMALSOLUTIONSLogarithmicperformanceguaranteesForquiteanumberofNP-hardcombinatorialoptimizationproblems,noap-proximationalgorithmisknownthathasaconstantperformanceguarantee.Thenextbestalternativeistogiveanapproximationalgorithminwhichtheper-formanceguaranteeisaslowlygrowingfunctionoftheinputsize.Onenaturalclassofguaranteesiswhentheproblemcanbesolvedwithinalogarithmicorpolylogarithmicfactorofoptimal.Inthissection,weshallpresentseveralresultsofthistype.Intheminimum-costsetcoveringproblemwearegivenafamilyofsetsFfSSSmgwhereSifngimandnon-negativecostsciimandwewishtoselectasubsetFFsuchthatS2F0SfngsoastominimizethetotalcostofthesetsinFConsiderthefollowinggreedyalgorithm:weiterativelybuildasetcoverbyselectinganadditionalsetineachiterationuntiltheunionincludesallelementsfngineachiteration,wecomputethemarginalcostofcoveringanewelementforeachset:theratioofitscosttothenumberofitselementsthatwerenotintheunionofthesetsalreadyselected;wechoosethesetSiforwhichthemarginalcostissmallest,andincludeitinthecover.Johnson(1974a)andLovaszindependentlyshowedthatthegreedyalgorithmisanHn)-approximationalgorithmforthecaseinwhicheachcostciiswheretheharmonicfunctionHnisatmostlnnChvatalshowedthatitalsoisanHn)-approximationalgorithminthecaseofarbitrarynon-negativecosts.Infact,thegreedyalgorithmcanbeviewedasaprimal-dualalgorithm.Ifoneconsidersthenaturallinearprogrammingrelaxationofthisproblem,minimizemXicixisubjecttoXijSixiforeachjn;xiforeachim;thenitsdualismaximizenXjyjsubjecttoXjSiyjciforeachim;yjforeachjn:

DAVIDB.SHMOYSAsthegreedyalgorithmconstructsanintegerprimalsolution,wecanviewitascomputingadualsolutionaswell:iftheelementjisrstcoveredintheiterationinwhichSiisselectedandtheassociatedmarginalcostisci=kthensetyjci=kItisclearthatbysettingthedualvariablesinthiswaythedualobjectivefunctionvalueisexactlyequaltothecostofthesetcovercomputed.However,thisdualsolutionisnotfeasible.ThecruxoftheperformanceguaranteeisthatifwesetyjinsteadtocikHnthenthisisafeasibledualsolution.LundYannakakishavegiventherstsignicantevidencethatnoapproximationalgorithmfortheunweightedsetcoverproblemcanperformsub-stantiallybetterthanthegreedyalgorithm.UsingaresultofFeigeLovasztheyshowedthatifthereexistsalogn-approximationalgorithmwiththenNPDTIMEnpolylogn(Incomparison,theconstantforthegreedyalgorithmisroughlyBellare,Goldwasser,Lund,Russellshowedthatnon-approximabilityresultsfortheunweightedsetcoverproblemcanbeobtainedbasedonweakercomplexityassumptions:theyshowedthatnoconstantperformanceguaranteeexistsunlessP=NPandtheyshowedthat,unlessNPDTIMEnloglogntheredoesnotexistalogn-approximational-gorithmforanyThereareseveralproblemsknowntobeequivalenttothesetcoveringproblem,intermsoftheperformanceguaranteesthatcanbeobtained.Mostinterestingamongtheseistheminimumdominatingsetproblem.Oneofthemostimportantrecentbreakthroughsinobtainingapproximationalgorithmswitha(poly)logarithmicperformanceguaranteeisfortheproblemofndingbalancedcutsingraphs.GivenanundirectedgraphGVEacutSVis-balancedifminfjSjjSjgjVjwhereSdenotesVSIfwearegivenGalongwithanonnegativecostceforeacheEtheminimum-cost-balancedcutistonda-balancedcutSsoastominimizePeSceTheseminalpaperofLeightonRaoshowedhowtoobtain,foranyconstantsanda-balancedcutthathascostO(logntimesthecostofanoptimal)-balancedcut.LeightonRaoalsodemonstratedthatthisisafundamentalprimitiveinthedesignofapproximationalgorithms,bygivingabroadrangeofapplicationsofthisalgorithmtoavarietyofotheroptimizationproblems.TheapproximationalgorithmofLeightonRaothatndsbalancedcutsisbasedonanalgorithmtondgoodquotientcutsMorepreciselyweinsteadfocusonndingasetSVsoastominimizePeSceminfjSjjSjgObservethatifwehaveanyalgorithmtonda\good"cutinagraph,wecanusethisrepeatedlytonda3-balancedcutSasfollows.IniterationindacutSiandaddthesmallerofSiandSitothecurrentcutStherebydeletingtheseverticesfromtheremaininggraph.SincethesmallerofSiorSialwayshasatmosthalfthevertices,wecanbesurethatatsomepointthecurrentcutShasbetweenjVjandjVjvertices;thatis,itis3-balanced;whenthishappens,thealgorithmterminates.Bytryingtondaminimumquotientcutineachiteration,weareadoptingagreedystrategyinmuchthesamewayas

COMPUTINGNEAR-OPTIMALSOLUTIONSwefoundgoodsolutionsforthesetcoveringproblem.UnfortunatelyndingtheminimumquotientcutisanNP-hardproblem,butndinganO(lognapproximationalgorithmforitsucestoprovethetheoremaboutbalancedcutsgivenabove.Infact,LeightonRaoactuallyfocusonanothercutproblem,inwhichtheobjectiveistondacutthatminimizesPeScefjSjjSjgAsfarasapproximationalgorithmsareconcerned,thisnewproblemisasymptoticallyequivalenttothequotientcutproblem,sincethemaxfjSjjSjgvariesbylessthanafactorofoverallcutsSTheadvantageofdealingwiththisnewobjectiveisthatitisthecombinatorialdualofamulticommodityowproblem,wherewewishtosendoneunitofowbetweeneachpairofverticessubjecttojointcapacityconstraintsceforeacheEanditisthisconnectionthatdrivestheirapproximationalgorithm.Beforegivingamoredetaileddiscussionofthewayinwhichndingnear-optimalbalancedcutsandmulticommodityowsarerelated,weshalldiscussacoupleoftheapplicationsofndingwell-balancedcuts.OneoftheprinciplemotivationswastogiveecientsimulationsofPRAMsonarbitrarynetworks.Thefactthattheperformanceguaranteeoftheapproximationalgorithmisloga-rithmiciscrucialinthissetting,sincethismakesitpossibleforthesimulation'srunningtimetoremainpolylogarithmic.Weshall,however,focusinsteadonapplicationstospeciccombinatorialoptimizationproblems.IntheminimumcutlineararrangementproblemwearegivenagraphGandtheaimistoindexthenverticesfngsoastominimizethemaximumofjSjforallcutsSoftheformfjgLetOPTLAGdenotethevalueoftheoptimalsolutionforagivengraphGThefollowingisanO(lognapproximationalgorithmforthisproblem,thatworksbydivide-and-conquer:nda(good)3-balancedcutSorderalloftheverticesofSbeforethever-ticesofSandrecurseoneachofSandStocomputetherestoftheorder.ObservethatGhasa2-balancedcutofvalueatmostOPTLAGtaketheoptimalsolutiontotheminimumcutlineararrangementproblem,andconsiderthecutgivenbySfbn=cgHencetheinitialcallproducesacutwithO(lognOPTLAGedges.IfweconsideranycutSfjgwithrespecttothenalordercomputed,eachedgeinSiscontributedbysomeleveloftherecursion,andthenumberofedgesfromeachlevelisO(lognOPTLAGThebalancingconditionensuresthatthereareO(lognlevelsofrecursion.Similardivide-and-conquerstrategiesdriveeachoftheapplicationsofndingbalancedcutstoderiveapproximationalgorithms.AnotherniceapplicationgivenbyLeightonRaoistoobtainanO(logn)-approximationalgorithmfortheminimum-costfeedbackarcsetproblemgivenadirectedgraphGVAwhereeacharcaAhasanassociatednonnegativecostcandasetofarcsFAsuchthatthegraphGVAFisacyclic,soastominimizethetotalcostofthearcsinFPaFcaTheanalogousdirectedcutistondarcstodeletesuchthattheresultinggraphisdividedintowell-balancedstrongly

DAVIDB.SHMOYSconnectedcomponents,whichmight,atrstglance,appearlessnatural.Klein,Agrawal,RaviRaolatergaveotherapplications,mostnotablyfortheproblemofcomputinggoodpivotingstrategiesinGaussianeliminationtominimizell-in.Intheremainderofthissection,wewishtobrieysketchtheideasbehindtheseresults,andinparticularexploretheconnectionbetweensuchcutprob-lemsandmulticommodityow.Forillustrativepurposes,wefocusonacloselyrelatedcutproblem,whichweshallcalltheminimum-costmulticutproblemWearegivenagraphGVEwhereeachedgeeEhasanon-negativecostcealongwithkpairsofnodesstsktkwewishtopartitiontheverticesintoanynumberofparts,VVlsuchthatsiandtiareindierentparts,foreachiksoastominimizethetotalcostofedgeswithendpointsindif-ferentparts.Ifkthisisthestandardminimumcutproblem,forundirectedgraphs.Acombinatoriallydualproblemisthemaximummulticommodityowproblemgiventhesameinput,ndaowfibetweensiandtiofvalueisuchthat,foreachedgeethetotalowonePkifieisatmostcesoastomaximizethetotalowvalue,PkiiOnceagain,ifkthisisthestandardmaximumowproblem.Ofcourse,inthiscase,thereisthecelebratedmax-owmin-cuttheoremofFordFulkersonthatstatesthatthevalueofthemaximumowisequaltothevalueoftheminimum-costcut.ThistheoremdoesnotgeneralizetolargerkHowever,theweakdualityrelationshipstillholds:ifthereisamulticutofcostthenclearlyanymulticommodityowhasvalueatmostTheminimumcostmulticutproblemisNP-hard.Themaximummulticom-modityowproblemisalinearprogram,andhencecanbesolvedinpolynomialtime.Note,however,thatunlikethesinglecommodityowproblem,thereneednotexistanoptimalsolutiontothislinearprogramthatisintegral.Thelin-earprogrammingdualofthemaximummulticommodityowproblemcanbeexplainedasfollows.ImaginetheinputgraphGasasystemofpipes,corre-spondingtotheedges,wherethecrosssectionofthepipecorrespondingtoedgeehasareaequaltoceForeachedgeethereisanonnegativedualvariableewhichcanbeviewedasthelengthofthecorrespondingpipe.Thus,thetotalvolumeWofthepipesystemisPeEceeSupposethatthereisamulticommodityowoftotalvalueLetdidenotethelengthoftheshortestpath(withrespecttobetweenthesourcesianditscorrespondingsinktitheneachunitofowbetweensiandtimustuseatotalvolumeofdiasittravels.Hence,ifwespecifythelengthfunctioninunitssuchthatminidithenitisclearthatthevalueofamaximummulticommodityowisatmostthetotalvolumeWTheduallinearprogramistocomputethelengthfunction(scaledsuchthatminidisothatthetotalvolumeofthesystemisminimized.Bythedualitytheoremoflinearprogramming,thevalueofthemaximummulticommodityowisequaltotheminimumvolumeWGarg,Vazirani,Yannakakisgiveanalgorithmthattakesasinputa

COMPUTINGNEAR-OPTIMALSOLUTIONSpipesystemofvolumeWandcomputesamulticutofcostO(logkWSincewecancomputeapipesystemoftheoptimalvolumeWinpolynomialtime,wecanthenobtainamulticutofcostO(logkWO(logkHowever,sinceisalowerboundonthecostoftheminimummulticut,weseethatthisyieldsanO(logk)-approximationalgorithmfortheminimum-costmulticutproblem.Wenextsketchtheproceduretocomputeamulticut,givenapipesystemofvolumeWwithaparticularlengthfunctionIniterationlthealgorithmcomputesasubsetofverticesVlsuchthatVldoesnotcontainbothsiandtiforeachikandforatleastoneofthesepairs,sjandtjcontainsexactlyoneofsjandtjTheseverticesaredeleted,andthisyieldsasmallerpipesysteminducedbytheremainingvertices.Thealgorithmcontinuestopartitiontheremainingverticesuntilallsource-sinkpairsareseparatedbythecurrentmulticut.Ineachiteration,choosesomesiandtithatarestillunseparated.Considerasphereofsomexedradiusraroundsiinthepipesystem:morepreciselytakethatpartofthepipesystemthatiswithindistancerofsiwithrespecttoThepartofthemulticutVlchoseninthisiterationisthesetofverticesthatareinsidethesphereforajudiciouschoiceofradiusrImagineaddingapoint\volume"ofvalueW=katsithenrissettothesmallestvaluesuchthatlnktimesthevolumeinsidethesphereisgreaterthanthetotalcostofthecutdened.Astraightforwardcomputationshowsthatrandhencenosource-sinkpairiscontainedwithinthesphere:eachsuchpairisatleastdistanceapart.Thus,thealgorithmeventuallyproducesamulticut.Thiscalculationinvolvesthesolutionofadierentialequation:observethatthevalueofthecutdenedbythesphereofradiusristhederivativeofthevolumecontainedasafunctionofrFinallythetotalcostofthemulticutfoundcanbeboundediterationbyiteration:theedgesaddedtothemulticutineachiterationhavecostatmostlnktimesthevolumeofthesphere.ThetotalvolumeofthepipesystemisatmostWandthetotalofthe\point"volumesaddedisatmostWandsothetotalcostofthemulticutisatmostlnkWSincethepublicationofthepaperbyLeightonRaotherehasbeenagreatdealofworkinextendingtheirworktomoregeneralsettings.ThereaderisreferredtothesurveyofTardosforanannotatedbibliographyoftheseresults.VeryrecentlyChungYauclaimtohaveobtainedapolynomial-timealgorithmbasedondierenttechniquesthatproducesa1/3-balancedcutofcostwithinaconstantfactoroftheoptimal)-balancedcut.Itremainsaninterestingproblemtoderivetrueapproximationalgorithmsfortheseproblems,inthesensethatthecutproducedhascostclosetotheoptimalcutwiththesamebalancerestriction.Furthermore,forthevariouscutproblemsdiscussedabove,aswellastheapplicationsofthem,nonon-triviallowerboundsareknownfortheperformanceguaranteesthatcanbeobtained.

DAVIDB.SHMOYSApproximationsAlgorithmswithSmallAbsoluteErrorBoundsIntheprecedingsections,wehaveprimarilyfocusedonthedesignandanal-ysisof-approximationalgorithms.Forsomeproblems,thisisnotthemostappropriatetypeofperformanceguarantee.Forexample,considerthebin-packingproblemwearegivennpieceswithspeciedsizesaaansuchthataaanwewishtopackthepiecesintobins,whereeachbincanholdanysubsetofpiecesoftotalsizeatmostsoastominimizethenumberofbinsused.Todecideiftwobinssuceisexactlythepartitionproblem,andhenceisNP-complete.Thus,therecannotexista-approximationalgorithmforanyunlessP=NPHowever,considertheFirst-Fit-Decreasingalgorithm,wherethepiecesarepackedinorderofdecreasingsize,andthenextpieceisalwayspackedintotherstbininwhichitts.IfFFDIdenotesthenumberofbinsusedbythisalgorithmoninputIandOPTBPIdenotesthenumberofbinsusedintheoptimalpacking,thenJohnson(1974a)provedthatFFDIOPTBPIforanyinputIYuehassubsequentlyclaimedthatFFDIOPTBPIwhich,incidentallyimpliesthatitisa3/2-approximationalgorithm.Thus,signicantlystrongerresultscanbeobtainedbyrelaxingthenotionoftheperformanceguaranteetoallowforsmalladditiveterms.Infact,itiscompletelyconsistentwithourcurrentunderstandingofcomplexitytheorythatthereisanalgorithmthatalwaysproducesapackingwithatmostOPTBPIbins.Whyisitthatwehavebotheredtomentionhardnessresultsoftheform,\theredoesnotexista-approximationalgorithmunlessP=NPifsucharesultcanbesoeasilycircumvented?Thereasonisthatforalloftheweightedproblemsthatwehavediscussed,anydistinctionbetweenthetwotypesofguaranteesdisappears;anyalgorithmguaranteedtoproduceasolutionofvalueatmostOPTccanbeconvertedtoa-approximationalgorithm.Eachoftheseproblemshasanaturalrescalingproperty:foranyinputIandanyvaluewecanconstructanessentiallyidenticalinstanceIsuchthattheobjectivefunctionvalueofanyfeasiblesolutionisrescaledbySuchrescalingmakesitpossibletoblunttheeectofanysmalladditivetermcintheguarantee,andmakeiteectivelyObservethatthebin-packingproblemdoesnothavethisrescalingproperty;thereisnoobviouswayto\multiply"theinstanceinawaythatdoesnotblurthecombinatorialstructureoftheoriginalinput.(ThinkaboutwhathappensifyouconstructanewinputthatcontainstwocopiesofeachpieceofIThus,wheneverweconsiderdesigningapproximationalgorithmsforanewcombinatorialoptimizationproblemitisimportanttoconsiderrstwhethertheproblemdoeshavetherescalingpropertysincethatwillindicatewhatsortofperformanceguaranteetohopefor.ThereareniceexamplesofNP-hardoptimizationproblemsforwhichapprox-

COMPUTINGNEAR-OPTIMALSOLUTIONSimationalgorithmsareknownthatalwaysdeliversolutionsofvaluewithinofoptimal:theedgecoloringproblemandtheminimummax-degreespanningtreeproblem.IntheedgecoloringproblemwearegivenanundirectedgraphGVEandwewishtoassignacolortoeachedgeofGsothatnotwoedgeswithacommonendpointareassignedthesamecolor,soastominimizethenumberofcolorsused.VizingshowedhowtocoloreachgraphGwithGcolors,whereGisthemaximumnumberofedgesincidenttoavertex.SinceGcolorsarecertainlyneeded,thisalgorithmneverusesmorethanoneadditionalcolorbeyondwhatisoptimal.Muchlater,HolyershowedthatthisproblemisNP-hard;infact,heshowedthatrecognizingwhetheragraphcanbeedge-coloredwiththreecolorsisNP-hard,andhenceno-approximationalgorithmexistsforanyunlessP=NPThereisstillaninterestingopenquestionconcerningedgecoloring:doesthereexistananalogousalgorithmformultigraphs?ItispossiblethatlinearprogrammingcanprovideananalogueoftheresultofVizingLetMdenotethesetofallmatchingsinagivenmultigraphGVEandconsiderthefollowinglinearrelaxationoftheedgecoloringproblem:minimizeXM2MxMsubjecttoXMMeMxMforeacheExMforeachMMSeymourhasconjecturedthattheoptimalvalueofthislinearprogramisatmostofromtheintegeroptimumOfcourse,evenifhisconjectureweretrue,weareaskingforsomethingstronger:wewouldlikeapolynomial-timealgorithmtondsuchacoloring.Incidentallyeventhoughthislinearprogramhasanexponentialnumberofvariablesitcanstillbesolvedbytheellipsoidalgorithm,sincetheseparationalgorithmrequiredtosolveitsdualisjustamaximum-costmatchingalgorithm.Intheminimummax-degreespanningtreeproblemwearegivenagraphGandwishtondaspanningtreeTofGsuchthatTisminimized.SincedecidingifthereisaspanningtreeofmaximumdegreeisjusttheHamiltonianpathproblem,theredoesnotexista-approximationalgorithmforthisproblemforanyunlessP=NPHowever,FurerandRaghavacharigaveanelegantalgorithmthatalwaysproducesaspanningtreeofmaximumdegreewithinofoptimal.Wereturnnowtothebin-packingproblem.Thebestknownapproximationalgorithm,duetoKarmarkarKarpwhobuildonworkbyFernan-

DAVIDB.SHMOYSdezdelaVegaLuekerdeliversasolutionthatusesOPTBPIO(logOPTBPIbins.Thisisarathersurprisingresult,andreliesonlinearprogramminginaninterestingwaySupposethatwegrouppiecesofidenticalsize,sothattherearebpiecesofthelargestsizesbofthesecondlargestsizesbmpiecesofthesmallestsizesmWeshalldescribeanintegerprogrammingformulationduetoEisemannConsiderthewaysinwhichasinglebincanbepacked.Oneofthesepackingscanbedescribedbyanm-tuplettmwheretiindicatesthenumberofpiecesofsizesiincluded.WeshallcallsuchanmtupleacongurationifPitisiTheremightbeanexponentialnumberofcongurations.Forexample,ifsm=kthenthenumberofcongurationscanbeupper-boundedbymkkLetNdenotethenumberofcongurations,andletTTNbeacompleteenumerationofthem,wheretijdenotesthejthcomponentofTiThissuggeststhefollowingformulation:minimizeNXjxjsubjecttoNXjtijxjbiforeachim;xjNforeachjNThisformulationwasintroducedinthecontextofdesigningpracticalalgorithmstondoptimalsolutionstocertainbin-packingproblems.Weshallrstpresentanalgorithmthat,foranygivenndsapackingwithatmostOPTBPIOpbins,wherepissomepolynomialfunction.Supposethatwendanoptimalextremepointofthelinearrelaxationofthisformulation.Itmusthaveatmostmnon-zerocomponents,andsoifwesimplyroundupthissolution,thenwehaveobtainedanintegersolutionofsizeatmostOPTBPImSincemisthenumberofdistinctpiecesizes,thenameofthegameinusingthisformulationistorstroundtheinstancesoastoreducemToimplementthisapproach,wemustalsobeabletosolvethelinearprogram.FernandezdelaVegaLuekerobservedthatitiseasytoignoresmallpiecesofsizeatmostsincetheycanbeaddedlatertothepackinginawaythatcertainlydoesnotintroducetoomucherror.ThisimpliesthatthereareOmvariables;hencethelinearprogramfortheremainingpiecescanbesolvedinpolynomialtime.FernandezdelaVegaLuekerpresentalineargroupingschemetoreducethenumberofdistinctpiecesizes.Thisschemeworksasfollows,andisbasedonaparameterkwhichwillbesetlater.Groupthepiecesofthe

COMPUTINGNEAR-OPTIMALSOLUTIONSgiveninputIasfollows:therstgroupconsistsoftheklargestpieces,thenextgroupconsistsofthenextklargestpieces,andsoon,untilallpieceshavebeenplacedinagroup.Thelastgroupcontainshpieces,wherehkTheroundedinstanceIisconstructedbydiscardingtherstgroup,andforeachothergroup,roundingthesizeofitspiecesuptothesizeofitslargestpiece.ItiseasytoseethatOPTBPIOPTBPIOPTBPIksignicantlywecanquicklytransformanypackingofIintoapackingofIusingatmostkadditionalbins(forthediscardedpieces).Thenumberofdis-tinctpiecesizesislessthann=kwherenisthenumberofpieces;ifwesetkdSIZEIewhereSIZEIPiaiOPTBPIthenweseethatn=kConsequentlyifwegroupthepiecesinthiswaysolvethelinearprogram,andthenroundupthissolution,weobtainapackingthatusesatmostOPTBPIbins.Furthermore,thenumberofconstraintsandvariablesofthelinearprogramisnowjustaconstant(thatdependsexponentiallyonKarmarkarKarpimproveboththerunningtimeofthisgeneralapproach,anditsperformanceguarantee.Themoretechnicalimprovementistheformer,wheretheyshowhowtheellipsoidalgorithmcanbeusedtoapproxi-matelysolvethislinearprogramwithinanadditiveerrorofintimeboundedbyapolynomialinmandlog(n=anThisimpliesthattheapproximationschemedescribedabovecannowbeimplementedtorunintimeboundedbyapolynomialinandthesizeoftheinput.Moresignicantlytheygiveamoresophisti-catedgroupingschemethatimpliesmuchstrongerperformanceguarantees.WewillshowhowtousethisschemetoobtainalgorithmthatndsapackingwithOPTIO(logOPTIbins.Notethatwecanassume,withoutlossofgeneralitythatan=SIZEIsincesmallerpiecescanagainbepackedlaterwithoutchangingtheorderofmagnitudeoftheabsoluteerror.Thegeometricgroupingschemeworksasfollows:processthepiecesinorderofdecreasingsize;closethecurrentgroupwheneveritstotalsizeisatleastandthenstartanewgroupwiththenextpiece.Letrdenotethenumberofgroups,letGidenotetheithgroup,andletnidenotethenumberofpiecesinGiObservethatforirwehavethatniniAsbefore,fromagiveninputIweformanewinstanceIwhereanumberofpiecesarediscardedandpackedseparatelyForeachirweputnipiecesinIofsizeequaltothelargestpieceinGiWediscardGGrandtheninismallestpiecesinGiirFirstofall,itshouldbeclearthatanypackingoftheroundedinstanceIcanbeusedtopackthosepiecesoftheoriginalinstancethatwerenotdiscarded.Wewillsketchtheproofoftwofurtherpropertiesofthisscheme:thenumberofdistinctpiecesizesinIisatmostSIZEIandthetotalsizeofalldiscardedpiecesisO(logSIZEITherstiseasy:eachdistinctpiecesizeinIcorrespondstooneofthegroupsGGreachofthesegroupshassize

DAVIDB.SHMOYSatleastandsothereareatmostSIZEIofthem.Toprovethesecondpropertysuppose,forthemoment,thateachgroupGihasatmostonemorepiecethanthepreviousgroupGiToboundthetotalsizeofthediscardedpieces,thetotalsizeofeachgroupisatmostandsothetotalsizeofGandGrisatmostFurthermore,thesizeofthesmallestpieceingroupGiisatmost=niSincewediscardapiecefromGiironlywhenGiistherstgroupthathasnipiecesandwediscarditssmallestpiece,thetotalsizeofthesediscardedpiecesisatmostPnrj=jHowever,sinceeachpiecehassizeatleast=SIZEInrSIZEIandsothetotalsizeofthediscardedpiecesisO(logSIZEIAnamortizedversionofthisargumentcanbeusedtoshowthatthesameboundholdsevenifthegroupsizesarenotsowellbehaved.Thegeometricgroupingschemecanbeusedtodesignanapproximationalgo-rithmthatalwaysndsapackingwithOPTBPIO(logOPTBPIbins.ThisalgorithmusesthegeometricschemerecursivelyThealgorithmappliesthegroupingscheme,packsthediscardedpiecesusingtheFirst-Fit-Decreasingalgorithm(orvirtuallyanyothersimplealgorithm),solvesthelinearprogramfortheroundedinstance,androundsthissolutiondowntoobtainapackingofasubsetofthepieces.Thisleavessomepiecesunpacked,andthesearehandledbyarecursivecalluntilthetotalsizeoftheremainingpiecesislessthanaspeciedconstant.LetIdenotetheoriginalinstance,letIdenotetheinstanceonwhichtherstlinearprogramissolved,andletIandIdenotethepiecespackedbasedontheintegerpartofthefractionalsolutionandthoseleftoverfortherecursivecall,respectivelyThekeytotheanalysisofthisalgorithmisthatLPILPILPILPIOPTBPIThisimpliesthattheonlyerrorintroducedineachlevelofrecursioniscausedbythediscardedpieces.SinceIistheleftovercorrespondingtothefractionalpartoftheoptimalsolution,itstotalsizeisatmostthenumberofconstraintsinthelinearprogram,whichisthenumberofdistinctpiecesizesinIthisisatmostSIZEIHencethesizeoftheinstancedecreasesbyafactorofineachlevelofrecursion,andsothereareO(logSIZEIlevels.Ineachoftheselevels,weuseO(logSIZEIbinstopackthediscardedpieces,andsoweobtaintheclaimedbound.Itwouldbeveryinterestingtoshowthatthebin-packingproblemcannotbeapproximatedwithinanadditiveerrorof(assumingthatPNPandtherecentprogressgivesnewhopethatsuchamodestgoalmightbeachieved.Ontheotherhand,itseemsentirelypossiblethatthereexistsanalgorithmwithconstantabsolutedeviationfromoptimal.Infact,evenwithoutanyrounding,itisnontrivialtoconstructinstancesforwhichtheoptimalvalueofthelinearprogrammingformulationdiersfromtheoptimalintegervaluebymorethanandnoresultreplacingthebyaiscurrentlyknown.

COMPUTINGNEAR-OPTIMALSOLUTIONSBeyondApproximationInthequartercenturythatperformanceguaranteesforapproximational-gorithmswereactivelystudied,notwoproblemsmorecompletelytypiedourfrustrationinmakingsubstantialprogressthanthemaximumcliqueproblemandtheminimumvertexcoloringproblem.AndfornotwoproblemshavetheimplicationsofthetheoremthatNP=PCP(logn;beenmoredramatic.Forthemaximumcliqueproblem,Johnson(1974b)proposedasimplegreedyheuristic.AcliqueKisconstructedbyrepeatedlyplacingavertexvofmaximumdegreeinKanddeletingvandeachvertexnotadjacenttovuntiltheentiregraphisdeleted.Johnson(1974c)showedthatifthegraphcanbevertexcoloredwithkcolors,thenitdeliversanindependentsetofsizeO(logknwherendenotesthenumberofverticesintheinputgraph.BoppanaHalldorssongaveanOn=logn)-approximationalgorithm,andthisisthebestresultknowntodate.LetOPTKGdenotethesizeofthemaximumcliqueinGAlthoughthemaximumcliqueproblemispurelycombinatorial,itdoeshavearescalingpropertyForanygraphGandconstantwecanconstructthegraphGbytakingdisjointcopiesofGandthenaddinganedgebetweeneachpairofverticesthatarisefromdierentcopiesofGClearlyOPTKGOPTKGandforanycliqueofsizekinGitinducesacliqueofsizekinoneoftheoriginalcopies.Thisimpliesthatthereisnoneedtoconsiderasymptoticperformanceguaranteesforthemaximumcliqueproblemthatintroducelowerordererrorterms.GareyJohnsondevelopedagraphcompositiontechniquetoshowthatifthereexistsa-approximationalgorithmforthemaximumcliqueproblemforsomeconstantthenthereexistsapolynomialapproximationscheme.LetGbethegraphformedbycomposingagraphGwithitself,inthesensethateachnodeofGisreplacedbyacopyofGandthereisanedgebetweenanypairofnodesincopiesofGthatcorrespondtoadjacentnodesinGNotethatOPTKGOPTKGandthatgivenacliqueofsizekinGonecanecientlyndacliqueofsizekinGByapplyinga-approximationalgorithmtoGwegetasetofsizeOPTKGwhichcanthenbeusedtondacliqueinGofsizeOPTKGByrepeatedlyapplyingthistechnique,wegettheclaimedresult.ThiswasthestateoftheartpriortotheworkofFeige,Goldwasser,Lovasz,Safra,SzegedywhoscaleddownthecharacterizationofNEXPofBabai,Fortnow,Lundtoshowthatthemaximumcliqueproblemdoesnothavea2-approximationalgorithm(andhenceapolynomialapproximationscheme)unlessNPDTIMEnO(loglognAroraSafrastrengthenedthistheoremtorelyontheassumptionPNPArora,Lund,Motwani,Sudan,Szegedyshowedthatthereexistsansuchthatnon-approximationalgorithmexistsunlessP=NPAlthoughwewillnotgivethedetails,wewillatleastindicatetheconnection

DAVIDB.SHMOYSbetweenholographicproofsandthecliqueproblem.AsinSectionconsideraprobabilisticverierforanNP-completelanguageLBuildagraphasfollows:foreachoftheroutcomesofthecointossesandeachofthekpossiblevaluesofthekholographicproofpositionsexamined,checkifthiscombinationleadstheveriertoaccept,andifso,constructavertexcorrespondingtothispair;twoverticesareadjacentiftheassociatedvaluesoftheproofareconsistent(i.e.,ifthetworandomstringscausethesamebitoftheprooftobeexamined,thentheassumedvalueofthatbitmustbethesameforbothvertices).IftheinputxLthentheexistenceofagoodholographicproofimpliesthatthereisacliqueKofsizerforeachoutcomeforthecointosses,letthevertexcorrespondingtoalongwiththecorrectbitsoftheholographicproofbeinKOntheotherhand,wewillshowthatifthereisacliqueKofsizelargerthanrthenthereexistsaholographicproofforwhichatleastrcointossescausetheveriertoaccept.Bythecorrectnessoftheverier,thatimpliesthatxLWecanconstructthisholographicproofunambiguouslybyextractingthevaluesasspeciedbythedescriptionoftheverticesinK(Somebitsoftheproofmaybeunspeciedbythis,buttheycanbechosenarbitrarily).SincethecointossescorrespondingtoverticesinKmustallbedistinct,thereareatleastjKjcointossesthatcausetheveriertoaccept.Ifthereisa2-approximationalgorithmforthecliqueproblem,wecoulddistinguishbetweenthecaseswhenthemaximumcliquesizeisatleastrandwhenitisatmostrandhencedecidewhetherxLinpolynomialtime,whichimpliesthatP=NPItisinterestingtonotethatBermanSchnitgerobservedthattheexistenceofann-approximationalgorithmforthecliqueproblem,forsomeconstantwouldyieldarandomizedpolynomialapproximationschemeforeachprobleminMAXSNPAlon,Feige,Wigderson,Zuckerman(unpub-lishedmanuscript)haverecentlyderandomizedthisconstruction;consequentlytheimpossibilityresultofArora,Lund,Motwani,Sudan,Szegedyforthemax-imumcliqueproblemcouldbederiveddirectlyfromtheirresultonthemaximumsatisabilityproblem.Thestateoftheartforthevertexcoloringproblempriortohadnotbeenmuchbetterthanforthemaximumcliqueproblem.Forthevertexcol-oringproblem,acorollaryoftheNP-completenessof3-colorabilityisthatno-approximationalgorithmcanexistwithTheminimumvertexcolor-ingproblemcanalsobeshowntohavearescalingpropertybyapplyingsimplegraphcompositiontechniques.GareyJohnsonuseamoreintricatecompositiontechniquetoprovethatanasymptoticperformanceguaranteelessthanwouldimplythatPNPJohnson(1974c)gavetherstnontrivialperformanceguarantee,byconsid-eringthefollowingalgorithm:untilallverticesaredeleted,repeatedlyndanindependentset(usingtheanalogueofgreedyalgorithmgivenaboveforthecom-plementaryproblem,themaximumcliqueproblem),coloritwithanewcolor,anddeleteitfromthegraph.Theboundfortheindependentsetalgorithm

COMPUTINGNEAR-OPTIMALSOLUTIONSimpliesthatOn=lognOPTCGcolorsareused,whereOPTCGdenotestheoptimalnumberofcolorsforGWigdersonobservedthatagraphGwithOPTCGcanbecol-oredwithOpncolorsbythefollowingsimplealgorithm:whilethemaximumdegreenodevhasdegreeatleastpncolorthe(bipartite)neighborhoodofvwith(unused)colors,deletethecolorednodesandrepeat;colortheremaininggraphwithpnadditionalcolorsbyrepeatedlycoloringanodewithsomecolornotusedatoneofitsneighbors.Sincetherstphasecanproceedforonlypniterations,onlypncolorsareusedintotal.Byusingthesameideatorecur-sivelycolorak-colorablegraphGi.e.,applyingtheapproximationprocedurefork1)-colorablegraphsuntilthemaximumdegreeissucientlysmall,Wigder-sonimprovedJohnson'sboundtoOn(loglogn(lognOPTCGTherehasbeenlittlesubsequentimprovement:afterconsiderableeort,thebestperfor-manceguaranteecurrentlyknownisonlyOn(loglogn(logn(Halldorsson,For3-colorablegraphs,BlumimprovedWigderson'salgorithm,andgaveaquitecomplicatedalgorithmthatuses\only"Onpolylogncolors.RecentlytherehasbeenafurtherstepforwardinthisdirectionbyKarger,Motwani,Sudan(unpublishedmanuscript),whorelyonanextensionofthemaximumcutalgorithmofGoemansWilliamsontoobtainacoloringwithOnlogncolors.Theydenearelaxationofthecoloringproblemcalledavectork-coloringeachvertexvisassignedann-dimensionalunitvectorxvsuchthatforanytwoadjacentverticesuandvxuxvkTheaimisndavectork-coloringforassmallavalueofkaspossible.Itisnothardtoshowthatanyordinaryvertexcoloringwithkcolorscanbeusedtoderiveavectork-coloring,byrelyingonthefactthattherealwaysexistkvectorswhosepairwiseinnerproductsareallkWegivenextthealgorithmtoroundthevectork-coloringintoatruecoloring.Thisroundingreliesonanintermediaryrelaxationofacoloring,whereatmostn=edgesarepermittedtohaveidenticalcolorsattheirendpoints.Suchanear-coloringmusthaveagraphinducedonn=nodeswithapropercoloring,andsowecanrecursivelyndagoodcoloringontheremaininggraph.Letdenotethemaximumdegreeofthegraph.Thenear-coloringisfoundbychoosingtlograndomhyperplanes,whichdividetheunitsphereintoatmosttregions.Thevectork-coloringisroundedtoanear-coloringbyassigningonecolortothevectorsineachregion.Infact,thisalgorithmhasasomewhatweakerperformanceguaranteethantheoneclaimedabove,butKarger,Motwani,SudangiveamoresophisticatedroundingtechniquetoobtainacoloringwithOnlognLundYannakakisshowedthattheproblemsofobtainingnear-optimalcliquesandnear-optimalcoloringwereintimatelyconnected.Inessence,theyshowedthatthereisanapproximationpreservingreductionfromthemax-imumcliqueproblem(restrictedtographsofthesortjustconstructedbythe

DAVIDB.SHMOYSproofabove)totheminimumvertexcoloringproblem.Consequentlythereex-istsansuchthatnon-approximationalgorithmforvertexcoloringexists,unlessP=NPAswiththeconstantlowerboundsforproblemsinMAXSNPthespecicvaluesforimpliedbytheproofswereinitiallyextremelysmallandhavesteadilyimproved.MostrecentlyBellareSudanshowedthatissucientforthemaximumcliqueproblem,andthatissucientfortheminimumvertexcoloringproblem.Theprincipleopenquestionremainingiswhetherthereexistssomesuchthatann-approximationalgorithmdoesexistforeachofthesetwoproblems.ItremainsatantalizingopenproblemtogiveanalgorithmthatcolorscolorablegraphswithO(logncolors.Thebestlowerboundsarequitefarfromthisleveltoo.Khanna,Linial,Safrashowthatitisnotpossibletogiveanalgorithmthatalwaysusescolors,unlessP=NPAcknowledgmentsIwouldliketothankthepeoplewhohavegivenmecom-mentsonpreliminaryversionsofthispaper:LeslieHall,DoritHochbaum,DavidJohnson,PhilipKlein,JonKleinberg,PaulMartin,RajeevMotwani,JoelWein,DavidWilliamson,andNealYoung.ReferencesM.AggarwalandN.GargAscalingtechniqueforbetternetworkdesign.InProceed-ingsofthe5thAnnualACM-SIAMSymposiumonDiscreteAlgorithmspagesA.Agrawal,PKlein,andR.RaviWhentreescollide:anapproximationalgorithmforthegeneralizedSteinerprobleminnetworks.InProceedingsofthe23rdAnnualACMSymposiumonTheoryofComputingpagesToappearinSIAMJ.Comput.S.Arora,C.Lund,R.Motwani,M.Sudan,andM.SzegedyProofvericationandhardnessofapproximationproblems.InProceedingsofthe33rdIEEESymposiumonFoundationsofComputerSciencepagesS.AroraandS.SafraProbabilisticcheckingofproofs.InProceedingsofthe33rdIEEESymposiumonFoundationsofComputerSciencepagesL.Babai,L.Fortnow,andC.LundNon-deterministicexponentialtimehastwo-proverinteractiveprotocols.ComputationalcomplexityM.BalinskiandK.SpielbergMethodsforintegerprogrammingalgebraic,combi-natorial,andenumerative.InJ.Aronofskyeditor,ProgressinOperationsResearch,IIIpagesWileyNewYork.R.Bar-YehudaandS.EvenAlineartimeapproximationalgorithmfortheweightedvertexcoverproblem.J.AlgorithmsM.Bellare,S.Goldwasser,C.Lund,andA.RussellEcientprobabilisticallycheck-ableproofsandapplicationstoapproximation.InProceedingsofthe25thAnnualACMSymposiumonTheoryofComputingpagesM.BellareandM.SudanImprovednon-approximabilityresults.InProceedingsofthe26thAnnualACMSymposiumonTheoryofComputingpagesPBermanandV.RamaiyerImprovedapproximationsfortheSteinertreeproblem.InProceedingsofthe3rdAnnualACM-SIAMSymposiumonDiscreteAlgorithmspagesPBermanandG.SchnitgerOnthecomplexityofapproximatingtheindependentsetproblem.InformationandComputationM.BernandPPlassmanTheSteinerproblemwithedgelengthsandInform.Process.Lett.

COMPUTINGNEAR-OPTIMALSOLUTIONSA.L.BlumAlgorithmsforapproximategraphcoloringPhDthesis,MIT,Cam-bridge,MA.R.B.BoppanaandM.M.HalldorssonApproximatingmaximumindependentsetsbyexcludingsubgraphs.BITN.ChristodesWorstcaseanalysisofanewheuristicforthetravellingsalesmanproblem.TechnicalReportGraduateSchoolofIndustrialAdministrationCarnegie-MellonUniversityPittsburgh,PA.F.R.K.ChungandS.T.YauAnearoptimalalgorithmforedgeseparators.InProceedingsofthe26thAnnualACMSymposiumonTheoryofComputingpagesV.ChvatalAgreedyheuristicforthesetcoveringproblem.Math.Oper.Res.D.-Z.DuandF.K.HwangAnapproachforprovinglowerbounds:solutionofGilbert-Pollak'sconjectureonSteinerratio.InProceedingsofthe31stAnnualIEEESym-posiumonFoundationsofComputerSciencepagesD.-Z.Du,Y.Zhang,andQ.FengOnbetterheuristicforEuclideanSteinermini-mumtrees.InProceedingsofthe32ndAnnualIEEESymposiumonFoundationsofCom-puterSciencepagesM.DyerandA.FriezeAsimpleheuristicforthep-centerproblem.Oper.Res.Lett.K.EisemannThetrimproblem.ManagementScienceR.FaginGeneralizedrst-orderspectra,andpolynomial-timerecognizablesets.InR.Karp,editor,ComplexityofComputations,AMSSymposiainAppliedMathematicsAMS,T.FederandD.H.GreeneOptimalalgorithmsforapproximateclustering.InProceedingsofthe20thAnnualACMSymposiumonTheoryofComputingpagesU.Feige,S.Goldwasser,L.Lovasz,S.Safra,andM.SzegedyApproximatingcliqueisalmostNP-complete.InProceedingsofthe32ndIEEESymposiumonFoundationsofComputerSciencepagesU.FeigeandL.LovaszTwo-proverone-roundproofsystems:theirpowerandtheirproblems.InProceedingsofthe24thAnnualACMSymposiumonTheoryofComputingpagesW.FernandezdelaVegaandG.S.LuekerBinpackingcanbesolvedwithininlineartime.CombinatoricaL.R.Ford,Jr.andD.R.FulkersonMaximalowthroughanetwork.CanadianJ.MathA.M.Frieze,G.Galbiati,andF.MaoliOntheworst-caseperformanceofsomealgorithmsfortheasymmetrictravelingsalesmanproblem.NetworksM.FurerandB.RaghavachariApproximatingtheminimumdegreespanningtreetowithinonefromtheoptimaldegree.InProceedingsofthe3rdAnnualACM-SIAMSymposiumonDiscreteAlgorithmspagesH.N.Gabow,M.X.Goemans,andD.PWilliamsonAnecientapproxima-tionalgorithmforthesurvivablenetworkdesignproblem.InProceedingsofthe3rdMPSConferenceonIntegerProgrammingandCombinatorialOptimizationpagesM.R.GareyandD.S.JohnsonThecomplexityofnear-optimalgraphcoloring.J.Assoc.Comput.Mach.N.Garg,V.V.Vazirani,andM.YannakakisApproximatemax-owmin-(multi)cuttheoremsandtheirapplications.InProceedingsofthe25thAnnualACMSymposiumonTheoryofComputingpagesE.N.GilbertandH.O.PollakSteinerminimaltrees.SIAMJ.Appl.Math.M.X.GoemansandD.J.BertsimasSurvivablenetworks,linearprogrammingrelaxations,andtheparsimoniouspropertyMath.Programming

DAVIDB.SHMOYSM.X.Goemans,A.V.Goldberg,S.A.Plotkin,D.B.Shmoys,E.Tardos,andD.PWilliamsonImprovedapproximationalgorithmsfornetworkdesignproblems.InProceedingsofthe5thAnnualACM-SIAMSymposiumonDiscreteAlgorithmspagesM.X.GoemansandD.PWilliamsonAgeneralapproximationtechniqueforconstrainedforestproblems.InProceedingsofthe3rdAnnualACM-SIAMSymposiumonDiscreteAlgorithmspagesToappearinSIAMJ.Comput.M.X.GoemansandD.PWilliamsonAnew3/4-approximationalgorithmforMAXSAT.InProceedingsofthe3rdMPSConferenceonIntegerProgrammingandCom-binatorialOptimizationToappearinSIAMJ.onDiscreteMath.M.X.GoemansandD.PWilliamson.878-approximationalgorithmforMAXCUTandMAX2SAT.InProceedingsofthe26thAnnualACMSymposiumonTheoryofComputingpagesR.L.GrahamBoundsforcertainmultiprocessinganomalies.BellSystemTech.J.M.M.HalldorssonAstillbetterperformanceguaranteeforapproximategraphcoloring.Inform.Proc.Lett.D.S.HochbaumApproximationalgorithmsforsetcoveringandvertexcoverprob-lems.SIAMJ.Comput.D.S.HochbaumandD.B.ShmoysAbestpossibleapproximationalgorithmforthek-centerproblem.Math.Oper.Res.I.HolyerTheNP-completenessofedge-coloring.SIAMJ.Comput.W.L.HsuandG.L.NemhauserEasyandhardbottlenecklocationproblems.DiscreteAppl.Math.F.K.HwangOnsteinerminimaltreeswithrectilineardistance.SIAMJ.Appl.Math.D.S.Johnson(1974a).Fastalgorithmsforbin-packingJ.Comput.SystemSci.D.S.Johnson(1974b).Approximationalgorithmsforcombinatorialproblems.J.Comput.SystemSci.D.S.Johnson(1974c).Worstcasebehaviorofgraphcoloringalgorithms.InProceedingsofthe5thSoutheasternConferenceonCombinatorics,GraphTheory,andComputingpagesUtilitasMathematicaPublishing,Winnipeg,Ont.D.S.JohnsonTheNP-completenesscolumn:anongoingguide.J.AlgorithmsN.KarmarkarandR.M.KarpAnecientapproximationschemefortheone-dimensionalbin-packingproblem.InProceedingsofthe23rdAnnualIEEESymposiumonFoundationsofComputerSciencepagesS.Khanna,N.Linial,andS.SafraOnthehardnessofapproximatingthechromaticnumber.InProceedingsofthe2ndIsraeliSymposiumonTheoryandComputingSystemspagesS.KhullerandU.VishkinBiconnectivityapproximationsandgraphcarvings.InProceedingsofthe24thAnnualACMSymposiumonTheoryofComputingpagesPKlein,A.Agrawal,R.Ravi,andS.RaoApproximationthroughmulticommodityow.InProceedingsofthe31stAnnualIEEESymposiumonFoundationsofComputerSciencepagesToappearinCombinatoricaPKleinandR.RaviWhencyclescollapse:ageneralapproximationtechniqueforconstrainedtwo-connectivityproblems.InProceedingsofthe3rdMPSConferenceonIntegerProgrammingandCombinatorialOptimizationpagesT.LeightonandS.RaoAnapproximatemax-owmin-cuttheoremforuniformmulticommodityowproblemswithapplicationstoapproximationalgorithms.InProceed-ingsofthe29thAnnualIEEESymposiumonFoundationsofComputerSciencepagesJ.K.LenstraandA.H.G.RinnooyKanThecomplexityofschedulingunderprecedenceconstraints.OperationsRes.

COMPUTINGNEAR-OPTIMALSOLUTIONSJ.K.Lenstra,D.B.Shmoys,andE.TardosApproximationalgorithmsforschedul-ingunrelatedparallelmachines.MathematicalProgrammingJ.H.LinandJ.S.Vitter-approximationswithminimumpackingconstraintviolation.InProceedingsofthe24thAnnualACMSymposiumonTheoryofComputingpagesL.C.LorentzenNotesoncoveringofarcsbynodesinanundirectedgraph.Tech-nicalReportORCUniversityofCalifornia,BerkeleyL.LovaszOntheratioofoptimalintegralandfractionalcovers.DiscreteMath.C.LundandM.YannakakisOnthehardnessofapproximatingminimizationprob-lems.InProceedingsofthe25thAnnualACMSymposiumonTheoryofComputingpagesG.L.NemhauserandL.E.Trotter,Jr.Vertexpacking:structuralpropertiesandalgorithmsMath.ProgrammingC.H.PapadimitriouComputationalcomplexityAddisonWesleyReading,MA.C.H.PapadimitriouandM.YannakakisOptimization,approximationandcom-plexityclasses.J.ComputerSys.SciencesC.H.PapadimitriouandM.YannakakisThetravelingsalesmanproblemwithdistancesoneandtwo.Math.Oper.Res.C.N.PottsAnalysisofalinearprogrammingheuristicforschedulingunrelatedparallelmachines.DiscreteAppl.Math.PRaghavanandC.D.ThompsonRandomizedrounding:atechniqueforprovablygoodalgorithmsandalgorithmicproofs.CombinatoricaD.J.Rosenkrantz,R.E.Stearns,andPM.LewisIIAnanalysisofseveralheuristicsforthetravelingsalesmanproblem.SIAMJ.Comput.S.SahniandT.GonzalezP-completeapproximationproblems.J.Assoc.Comput.Mach.D.B.ShmoysandE.TardosAnimprovedapproximationalgorithmforthegener-alizedassignmentproblem.MathematicalProgrammingD.B.ShmoysandD.PWilliamsonAnalyzingtheHeld-KarpTSPbound:amonotonicitypropertywithapplicationInformationProc.Lett.E.TardosApproximatemin-maxtheoremsandfastapproximationalgorithmsformulticommodityowproblems.InSummerSchoolonCombinatorialOptimizationpagesM.A.TrickSchedulingmultiplevariable-speedmachines.Unpublishedmanuscript.V.G.VizingOnanestimateofthechromaticclassofap-graph(inRussian).Diskret.AnalizA.WigdersonImprovingtheperformanceguaranteeforapproximategraphcolor-ing.J.Assoc.Comput.Mach.D.PWilliamson,M.X.Goemans,M.Mihail,andV.V.VaziraniAprimal-dualapproximationalgorithmforgeneralizedSteinernetworkproblems.InProceedingsofthe25thAnnualACMSymposiumonTheoryofComputingpagesToappearinCombinatoricaL.A.WolseyHeuristicanalysis,linearprogrammingandbranchandbound.Math.ProgrammingStud.M.YannakakisOntheapproximationofmaximumsatisabilityInProceedingsofthe3rdAnnualACM-SIAMSymposiumonDiscreteAlgorithmspagesToappearinJ.AlgorithmsM.YueAsimpleproofoftheinequalityFFDL OPTL8LfortheFFDbin-packingalgorithm.ActaMathematicaeApplicataeSinicaA.Z.ZelikovskyAn11/6-approximationalgorithmforthenetworkSteinerproblem.AlgorithmicaSchoolofOperationsResearchandIndustrialEngineering,CornellUniversity,Ithaca,NYE-mailaddressshmoys@cs.cornell.edu