資源描述:
《fastdeterministicparallelbranch-and-bound》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、FastDeterministicParallelBranch-and-BoundyzxKieranT.HerleyAndreaPietracaprinaGeppinoPucciAbstractThebranch-and-boundprobleminvolvesdeterminingtheminimumcostleafinacost-labelledtree,subjecttotheconstraintthatonlytherootisknowninitiallyandthatchildrenarerevealedonly
2、byvisitingtheirparent.Wepresenttherstecientdeterministicalgorithmtosolvethebranch-and-boundproblemforatreeTofconstantdegreeonap-processorparallelmachine.Letcbethecostoftheminimum-costleafinT,andletnandhbethenumberofnodesandtheheight,respectively,ofthesubtreeT
3、Tofnodesofcostlessthanorequaltoc.Ouralgorithmruns2inOn=p+hlog(np)timeonanEREW-PRAM.Moreover,therunningtimefaithfullyre
ectsbothcommunicationandcomputationcosts,unlikemostofthepreviousresultswherethecostoflocalcomputationisignored.Forlargerangesoftheparameters,o
4、uralgorithmmatchestheoptimalperformanceofexistingrandomizedstrategies.ThealgorithmcanbeportedtoanyarchitectureforwhichanecientimplementationofParallelPriorityQueues[PP91]isavailable.Keywords:Algorithmsanddatastructures,theoryofparallelanddistributedcomputation,co
5、mbinatorialoptimization,dynamicload-balancing.ContactAuthor:GeppinoPucciDepartimentodiElettronicaeInformatica,UniversitadiPadova,ViaGradenigo6/A,I-35131Padova,ITALYe-mail:geppo@artemide.dei.unipd.itfax:+39498277826yDepartmentofComputerScience,UniversityCollegeCor
6、k{NationalUniversityofIreland,Cork,Ireland.email:k.herley@cs.ucc.iezDipartimentodiMatematicaPuraeApplicata,UniversitadiPadova,Padova,Italy.email:andrea@artemide.dei.unipd.itxDipartimentodiElettronicaeInformatica,UniversitadiPadova,Padova,Italy.email:geppo@artemi
7、de.dei.unipd.it1IntroductionThesolutionofacombinatorialoptimizationproblemcanoftenbeobtainedbytheexplorationofatree,whoseinternalnodescorrespondtopartialsolutions(growingprogressivelymorerenedwithincreasingdepth)andwhoseleavescorrespondtofeasiblesolutions.Finding
8、asolutionofminimumcostinvolvessearchingthetreetoidentifyaminimum-costleaf.FormanyNP-hardoptimizationproblems,anexhaustivesearchoftheentiretreewouldbepro