您好,欢迎访问三七文档
THEPROBABILISTICANALYSISOFAHEURISTICFORTHEASSIGNMENTPROBLEMDavidAvisC.W.Lai*SchoolofComputerScienceMcGillUniversity805SherbrookeSt.W.Montreal,Canada,H3A2K6ABSTRACTWepresentaheuristictosolvethembymassignmentprobleminO(m2)time.TheassignmentproblemisformulatedasaweightedcompletebipartitegraphG=(S,T,E),|S|=|T|=m.Forconvenienceweassumethatmiseven.Themainpro-cedureintheheuristicistoconstructagraphGd=(S,T,Ed)whichisasubgraphofG,|Ed|=4dn,n=m2,suchthatwecanfindaperfectmatchinginGdwithprobabil-ityatleast1-13⎛⎝dn⎞⎠d2-4d-1.AnO(|S||E|)exactalgorithmisusedtofindaminimumweightmatchingMinGd.AnyunmatchedverticesinGrelativetoMarethenmatchedbyagreedyalgorithm.Theexpectedvalueofthetotalcostofthematchingfoundbytheheuristicisshowntobelessthan6ifthecostsareindependentandidenticallydistributeduniformlyintheunitinterval.Further,withtheaboveprobability,theheuristicproducesasolutionwhichisatmost6timestheoptimalsolution.KeyWords.AssignmentProblem,Heuristics,ProbabilisticAnalysisofAlgorithms,WeightedMatchings.1.IntroductionLetG=(S,T,E)bethecompletebipartitegraphwithvertexsetsSandTeachofcardinalitym,andEthesetofedgesbetweenSandT.Associatedwitheachedge(i,j)thereisaweightci,j.AmatchingMinGisasetofedgessuchthatnotwoedgesinMareincidenttothesamevertexofG.ThematchingisperfectifeachvertexinGisadjacenttosomeedgeinM.Aminimumweightperfect*CurrentAddress:G.P.O.2706,HongKong-2-matchingforGisaperfectmatchingforwhichthesumoftheedgeweightsisminimum.Theassignmentproblemistofindsuchaminimumweightmatching.ThereareexactalgorithmstosolvetheassignmentprobleminO(m3)time[10].Karp[7]hasfoundanalgorithmthatfindsanoptimalsolutioninexpectedtimeO(n2logn).Severalheuristicsexistfortheassignmentproblem[8],[6],[1][3].Asurveyofheuristicsfortheweightedmatchingproblemandsomeapplicationsiscontainedin[2].Inordertoevaluatethesolutionsproducedbytheseheuristics,itisnaturaltoaskwhatistheexpectedsizeoftheoptimalsolution,givenaprobabilitydistributionfortheedgeweights.Iftheedgeweightsareindependentlydistributedontheunitinterval,Walkup[12]hasprovedthatthisexpectedvalueisboundedabovebytheconstant3,forallm,averyremarkableresult.TheideabehindWalkup’sproofistheconstructionofasparsesubgraphofGinwhichtheedgesallhavelowweight.HedefinesasubgraphGd,forsomesmallintegerd,bychoosingdedgesrandomlyfromeachvertexinSandT.In[13]itisshownthatwithprobabilityapproachingoneasmtendstoinfinity,thisgraphhasaperfectmatching.Thenaturalcandidateforsuchasubgraphwouldbetochooseforeachver-tex,thedsmallestweightedgesthatareincidentwithit.Unfortunatelythiswillnotwork,sincetheedgeschoseninsuchawaywillnotbeindependent.Consider,forexample,theminimumweightedgeinG.Itwillbechosentwice,oncebyavertexinSandoncebyavertexinT.Walkupavoidsthisproblembyusingaprobabilistictrick:eachedgeisreplacedbytwodirectededgeswithoppositedirections.Theweightsonthedirectededgesarechosenfromdistributionssuchthattheminimumofthetwoedgeweightsstillhasuniformdistributionontheunitinterval.Thisissufficientforprovingtheresultstated,butdoesnotprovideaconstructivemethodthatcanbeusedtoproduceaheuristic.Inthispaperweavoidthedependencyproblembyconstructingadifferentkindofrandomgraph.WeproveanaloguesofWalkup’sresultsforthisnewgraph.Itisshowntoalmostsurelyhaveaperfectmatch-ing,anditisshownhowtoconstructthisgraphdirectlyfromthegivenedgeweights.Weprovethattheperfectmatchingthusfoundhasexpectedweightatmost6.TheheuristicrunsinO(m2)timeandpro-ducesasolutionwhichwithprobabilityapproachingone,isatmost6timestheoptimumvalue.Thisistheonlyknownheuristicwithaconstantratiobound,withprobabilityapproachingone.Insection2theheuristicispresentedalongwithacomplexityanalysis.Insection3weshowthattherandomgraph-3-constructedbytheheuristichasaperfectmatchingwithprobabilityapproachingone.Thisisfollowedinsection4byaproofthattheexpectedweightofthematchingproducedislessthan6.Theresultsgiveninthispaperwerefirstpublishedinthesecondauthor’sMaster’sthesis[9].Thisthesisalsocontainsextensivenumericalresults.2.TheHeuristicForconvenienceweassumethatmisevenandsetn=m/2.Theheuristicissuppliedwithaninte-gerparameterdwhichmustbeatleast5.Thisparametercontrolsthequalityofthesolutionandthecostofthecomputation.Inpractice,settingd=5appearstobemostsatisfactory.Thealgorithmconsistsofthreesteps:-TheconstructionofasparsedirectedrandomgraphGdwith4dnedges;-ThesolutionofthemaximumcardinalityminimumweightmatchingproblemintheundirectedgraphobtainedbyignoringthedirectionsonedgesofGd;-ThematchingofanyunmatchedverticesinGdusingagreedyheuristic.Step-1.(ConstructionofadirectedgraphGd=(S1∪S2,T1∪T2,Ed)with4dnedges,seeFigure1.)PartitionSandTintosubsetsS1,S2andT1,T2eachofcardinalityn.Forv∈Si,i=1,2N(v)={w∈Ti|cv,wisoneofthedsmallestedgeweightsincidentv}.Forw∈Ti,i=1,2N(w)={v∈S3-i|cv,wisoneofthedsmallestedgeweightsincidentw}.SetEd={(v,w)|v∈Si∪Ti,w∈N(v),i=1,2}.Step-2.(FindaminimumweightmatchinginGd.)ApplyanO(|S||E|)minimumweightmatchingalgorithmtoGdignoringthedirectionsontheedges.LetMdbetheresultingmatching.-4-Step-3.(MatchtheunmatchedverticesinGdbyagreedyalgorithm.)S*={unmatchedverticesinSrelativeMd}.T*={unmatchedverticesinTrela
本文标题:The probabilistic analysis of a heuristic for the
链接地址:https://www.777doc.com/doc-3295267 .html