资源描述：
《a tight analysis of the greedy algorithm for set cover》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ATightAnalysisoftheGreedyAlgorithmforSetCoverPetrSlavkNovember19,1995AbstractWeestablishsigni cantlyimprovedboundsontheperformanceofthegreedyal-gorithmforapproximatingsetcover.Inparticular,weprovidethe rstsubstantialimprovementofthe20yearoldclassicalharmonicupperbound,
2、H(m),ofJohnson,Lo-vasz,andChvatal,byshowingthattheperformanceratioofthegreedyalgorithmis,infact,exactlylnm?lnlnm+(1),wheremisthesizeofthegroundset.Thedi erencebetweentheupperandlowerboundsturnsouttobelessthan1:1.Thisprovidesthe rsttightanalysisofthegreedyalgorithm,aswel
3、lasthe rstupperboundthatliesbelowH(m)byafunctiongoingtoin nitywithm.WealsoshowthattheapproximationguaranteeforthegreedyalgorithmisbetterthantheguaranteerecentlyestablishedbySrinivasanfortherandomizedroundingtechnique,thusimprovingtheboundsontheintegralitygap.Ourimprovemen
4、tsresultfromanewapproachwhichmightbegenerallyusefulforattackingothersimilarproblems.Keywords:ApproximationAlgorithms,CombinatorialOptimization,FractionalSetCover,GreedyAlgorithm,PartialSetCover,SetCover.DepartmentofMathematics,StateUniversityofNewYorkatBu alo,Bu alo,NY14
5、214,USA.E-mail:slavik@math.buffalo.eduPetrSlavk,SetCover,November19,199511IntroductionSetcoverisoneoftheoldestandmoststudiedNP-hardproblems([8],[4],[7],[9],[1],etc.).GivenagroundsetUofmelements,thegoalistocoverUwiththesmallestpossiblenumberofsets.Oneofthebestpolynomialt
6、imealgorithmsforapproximatingsetcoveristhegreedyalgorithm:ateachstepchoosetheunusedsetwhichcoversthelargestnumberofremainingelements.JohnsonandLovasz([7],[9])showedthattheperformanceratioofthegreedymethodisnoworsethanH(m),thwhereH(m)=1++1=misthemharmonicnumber,avaluewh
7、ichisclearlybetweenlnmandlnm+1.Chvatalin[1]extendedtheirresultstotheweightedversionoftheproblem.Other,morecomplexapproximationalgorithms,havealsobeenstudied.Forexample,Halldorsson'slocalimprovements"modi cationofthegreedyalgorithm([5],[6])improvedtheupperboundtoaboutH(
8、m)?0:43andsuggestedthatforlargegroundsetsthisimprovementcanbemadeevenstronger.Srinivasan'sanalys
