资源描述：
《A New Lower Bound Technique and its Application.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、SIAMJ.COMPUT.994SocietyforIndustrialandAppliedMathematicsVol.23,No.4,pp.834-851,August1994009ANEWLOWERBOUNDTECHNIQUEANDITSAPPLICATION:TIGHTLOWERBOUNDFORAPOLYGONTRIANGULATIONPROBLEM*PRAKASHRAMANANAbstract.Anewtechniqueforobtaininglowerboundsontheworst-casetime-complexityofoptimizationproblemsinthelin
2、eardecisiontreemodelofcomputationispresented.Thistechniqueisthenusedtoobtainatightf2(nlogn)lowerboundforaproblemoffindingaminimumcosttriangulationofaconvexpolygonwithweightedvertices.Thisproblemissimilartotheproblemoffindinganoptimalorderofcomputingamatrixchainproduct.Ifthelowerboundtechniquecouldbe
3、extendedtoboundeddegreealgebraicdecisiontrees,atightf2(nlogn)lowerboundforthislatterproblemwouldbeobtained.Keywords,optimizationproblem,time-complexity,algebraicdecisiontreemodel,lowerbound,polygontriangulation,matrixchainproductAMSsubjectclassifications.68Q25,68Q20,68Q051.Introduction.LetPbeanoptim
4、izationproblemwhoseinputinstancesarepoints(x,x2x,,)in(thepositiveorthantof)then-dimensionalrealspaceRn,forsomen>_1.LetS(P)bethefinitesetofsolutionsofP.AssociatedwitheachsES(P)isapolynomialcostfunctionCs(Y).Pcanbestatedasfollows:GivenERn,finds6S(P)suchthatcs()isassmallaspossible.Supposethateachs6S(P)
5、istheuniqueoptimalsolutionforsomeinstance6R".ThenIS(P)IisalowerboundonthenumberofleavesofanydecisiontreethatsolvesP.Thefollowingiswellknown.THEOREM1.AnydecisiontreethatsolvesPhasf2(logIS(P)I)height.Formanyproblems,thelowerboundobtainedusingtheabovetheoremisunsatisfac-tory.In2,wepresentanewtechniquef
6、orobtainingalowerboundontheworst-casetime-complexityofP,inthelineardecisiontreemodelofcomputation.In3,weusethistechniquetoobtainatightf2(nlogn)lowerboundforaproblemoffindingaminimumcosttriangulationofaconvexpolygonwithweightedvertices.Thisproblemissimilartotheproblemoffindinganoptimalorderofcomputin
7、gamatrixchainproduct.Ifwecouldextendourlower-boundtechniquetoboundeddegreealgebraicdecisiontrees,wewouldhaveatightf2(nlogn)lowerboundforthislatterproblem.In4,wepresentourconclusions.2.Thelower-boundte
