资源描述：
《fastdeterministicparallelbranch-and-bound》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、FastDeterministicParallelBranch-and-BoundyzxKieranT.HerleyAndreaPietracaprinaGeppinoPucciAbstractThebranch-and-boundprobleminvolvesdeterminingtheminimumcostleafinacost-labelledtree,subjecttotheconstraintthatonlytherootisknowninitiallyandthatchildrenarerevealedonly
2、byvisitingtheirparent.Wepresentthe rstecientdeterministicalgorithmtosolvethebranch-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(growingprogressivelymorere nedwithincreasingdepth)andwhoseleavescorrespondtofeasiblesolutions.Finding
8、asolutionofminimumcostinvolvessearchingthetreetoidentifyaminimum-costleaf.FormanyNP-hardoptimizationproblems,anexhaustivesearchoftheentiretreewouldbepro
