Average-case analyses of first fit and random fit

Average-CaseAnalysesofFirstFitandRandomFitBinPackingSusanneAlbersMichaelMitzenmacheryAbstractWeprovethattheFirstFitbinpackingalgorithmisstableundertheinputdistributionUfk2;kgforallk3,settlinganopenquestionfromtherecentsurveybyComan,Garey,andJohnson[3].Ourproofgeneralizesthemulti-dimensionalMarkovchainanalysisusedbyKenyon,Rabani,andSinclairtoprovethatBestFitisalsostableunderthesedistributions[10].OurproofismotivatedbyananalysisofRandomFit,anewsimplepackingalgorithmrelatedtoFirstFit,thatisinterestinginitsownright.WeshowthatRandomFitisstableundertheinputdistributionsUfk2;kg,aswellaspresentworst-caseboundsandsomeresultsondistributionsUfk1;kgandUfk;kgforRandomFit.1IntroductionIntheone-dimensionalbinpackingproblem,oneisgivenasequencea1;:::;an2(0;1]ofitemstopackintobinsofunitcapacitysoastominimizethenumberofbinsused.Agreatdealofliteraturehasfocusedonthisproblem,perhapsbecause,asComan,Garey,andJohnson[3]observeintheirrecentsurveyonbinpacking,\Theclassicalone-dimensionalbinpackingproblemhaslongservedasaprovinggroundfornewapproachestotheanalysisofapproximationalgorithms.Forexample,recentlythestudyofBestFitbinpackingunderdiscreteuniformdistributionshasledtoanovelanalysistechnique,basedonthetheoryofmulti-dimensionalMarkovchains.InthispaperweextendthisapproachtoanalyzeFirstFitandanewbinpackingalgorithm,calledRandomFit,underdiscreteuniformdistributions.FirstFitandBestFitaretwoclassicalalgorithmsforonlinebinpacking.WithFirstFit,thebinsareindexedinincreasingorderoftheircreation.Eachitemissequentiallyplacedintothelowestindexedbinintowhichitwillt,orintoaemptybinifnosuchbinisavailable.WiththeBestFitalgorithm,eachincomingitemisplacedintothenon-emptybinwithsmallestresidualcapacitythatcancontainit;ifnosuchbinexists,theitemisplacedinanemptybin.TheperformanceofFirstFitandBestFitintheworstcaseanduniformaveragecasehasbeensettledforquitesometime.Intheworstcase,thenumberofbinsusedbyanyofthesealgorithmsisatmost1710timestheoptimumnumberofbins,asshownbyJohnsonetal.[9].WhenitemsizesaregeneratedbyU(0;1),thecontinuousuniformdistributionon(0;1],thentheperformancemeasureofinterestistheexpectedwaste,whichisthedierencebetweenthenumberofbinsusedandthetotalsizeoftheitemspackedsofar.Shor[15]showedthattheexpectedwastecreatedbyFirstFitis(n2=3).Shor[15]andLeightonandShor[12]provedthatBestFitdoesbetter,generatingexpectedwaste(pnlog3=4n).Becauseofthesetightbounds,researchonFirstFitandBestFitisnowfocusedonanalyzingexpectedwastewhenitemsizesaregeneratedbydiscreteuniformdistributions.AdiscreteuniformMax-Planck-InstitutfurInformatik,ImStadwald,66123Saarbrucken,Germany.E-mail:[e-mail]ration,SystemsResearchCenter,PaloAlto,CA.AsubstantialportionofthisresearchdonewhileattheComputerScienceDepartment,UCBerkeley,undertheNationalScienceFoundationgrantNo.CCR-9505448.E-mail:[e-mail]12distribution,denotedbyUfj;kg;1jk,isonewhereitemsizesarechosenuniformlyfromthesetf1=k;2=k;:::;j=kg.ForUfk;kg,k1,FirstFitandBestFitachieveexpectedwaste(pnk)andO(pnlogk),respectively,(seeComanetal.[2]).SimilarboundsholdforUfk1;kg.Ofparticularinterestaredistributionsforwhichthealgorithmsarestable.Wesaythatanalgorithmisstableunderadistributioniftheexpectedwasteremainsbounded(thatis,O(1)),evenasthenumberofitemsngoestoinnity.Comanetal.[2]provedthatFirstFitisstableunderUfj;kg,whenkj2,andBestFitisstableunderUfj;kg,whenkj(j+3)=2.Later,Comanetal.[4]introducedanovelmethodforprovingthestability(andinstability)ofbinpackingalgorithmsbasedonmulti-dimensionalMarkovchains.TheirmethodologyallowedthemtoshowthatBestFitisstableunderUfj;kgforseveralspecicpairsofvaluesforjandk.Kenyonetal.[10]expandedonthisworkbyprovingthatBestFitisstableundertheentirefamilyofdistributionsUfk2;kg,usingacomplexanalysisoftheunderlyingMarkovchains.WebrieydescribetheMarkovchainsettingusedintheresultsdescribedabove.UsingtheBestFitalgorithmunderadiscreteuniformdistribution,apackingcanberepresentedbythenumberofbinsofeachpossibleresidualcapacity.Theorderofthebinsisirrelevant.ThispackingprocesscanthereforebeeasilyrepresentedbyaMarkovchain,wherethestateatanytimeisavectors=(s1;:::;sk1),andsiisthenumberofbinsofresidualcapacityi=k.TheBestFitalgorithmiswellsuitedtotheMarkovchainapproach,becausetheorderofthebinsisirrelevant,leadingtoasimplerepresentationofthepacking.Incontrast,intheFirstFitalgorithm,theorderofthebinscannotbedismissed.BecauseofthedicultyofrepresentingthestateintheFirstFitalgorithm,untilnowtheseMarkovchaintechniqueshavenotbeensuccessfullyappliedtotheFirstFitalgorithm.Inthispaper,weremedythisproblembydemonstratingaMarkovchainargumentthatshowsthatFirstFitisinfactstableunderthefamilyofdistributionsUfk2;kg.ThisresultdisprovesaconjecturemadebyComanetal.[3],whostatethatlimitedexperimentssuggestthattheexpectedwastemaygrowunboundedonUfk2;kgforsucientlylargek.Moreover,itdemonstratesthattheMarkovchainapproachmaybemoregenerallyapplicablethanpreviouslybelieved.Ourproofemergesfromananalysisofanewbinpackingalgorithm,calledRandomFit(RF).RandomFitisasimplerandomized