欢迎来到天天文库
浏览记录
ID:34425628
大小:133.91 KB
页数:10页
时间:2019-03-06
《polynomial time approximation schemes for euclidean tsp and other geometricproblemsnew》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、PolynomialTimeApproximationSchemesforEuclideanTSPandotherGeometricProblemsSanjeevAroraPrincetonUniversitytheTSP'snastiness(cf.PAbstractDcompleteness[37]andPLS-completeness[20]).WepresentapolynomialtimeapproximationschemeforButTSPinstancesarisinginpracticeareusuallyquit
2、eEuclideanTSPin2<.Givenanynnodesintheplanespecial,sothehardnessresultsmaynotnecessarilyapplytoand>0,thescheme®ndsa(1+)-approximationthem.InmetricTSPthenodeslieinametricspace(i.e.,thetotheoptimumtravelingsalesmantourintimeO(1=).ndistancessatisfythetriangleinequality).
3、InEuclideanTSPd2Whenthenodesareind<,therunningtimeincreasesto(ormoregenerally,inthenodesliein<4、metricTSP.approximationinpolynomialtime.Unfortunately,evenEuclideanTSPisNP-hard(Papadim-Wealsogivesimilarapproximationschemesforahostitriou[35],Garey,Graham,andJohnson[12]).ThereforeofotherEuclideanproblems,includingSteinerTree,k-TSP,algorithmdesignerswereleftwithnochoi5、cebuttocon-Minimumdegree-kspanningtree,k-MST,etc.(Thislistmaysidermoremodestnotionsofaªgood"solution.Karp[24],getlonger;ourtechniquesarefairlygeneral.)Theprevi-inaseminalworkonprobabilisticanalysisofalgorithms,ousbestapproximationalgorithmsforalltheseproblemsshowedthatw6、henthennodesarepickeduniformlyandachievedaconstant-factorapproximation.independentlyfromunitsquare,thenthe®xeddissectionAllouralgorithmsalsowork,withalmostnomodi®ca-heuristicwithhighprobability®ndstourswhosecostistion,whendistanceismeasuredusinganygeometricnormwithin1+7、ofoptimal(where>0isarbitrarilysmall).(suchasChristo®des[9]designedanapproximationalgorithmthat`forp1orotherMinkowskinorms).poneveryinstanceofmetricTSPcomputesatourofcostatmost1:5timestheoptimum.1IntroductionTwodecadesofresearchfailedtoimproveuponChristo®des'algorithmf8、ormetricTSP.Butsomere-searcherscontinuedtohopethatevenaPTASmightex-IntheTravelingSalesmanProblem(ªTSP"),weareg
4、metricTSP.approximationinpolynomialtime.Unfortunately,evenEuclideanTSPisNP-hard(Papadim-Wealsogivesimilarapproximationschemesforahostitriou[35],Garey,Graham,andJohnson[12]).ThereforeofotherEuclideanproblems,includingSteinerTree,k-TSP,algorithmdesignerswereleftwithnochoi
5、cebuttocon-Minimumdegree-kspanningtree,k-MST,etc.(Thislistmaysidermoremodestnotionsofaªgood"solution.Karp[24],getlonger;ourtechniquesarefairlygeneral.)Theprevi-inaseminalworkonprobabilisticanalysisofalgorithms,ousbestapproximationalgorithmsforalltheseproblemsshowedthatw
6、henthennodesarepickeduniformlyandachievedaconstant-factorapproximation.independentlyfromunitsquare,thenthe®xeddissectionAllouralgorithmsalsowork,withalmostnomodi®ca-heuristicwithhighprobability®ndstourswhosecostistion,whendistanceismeasuredusinganygeometricnormwithin1+
7、ofoptimal(where>0isarbitrarilysmall).(suchasChristo®des[9]designedanapproximationalgorithmthat`forp1orotherMinkowskinorms).poneveryinstanceofmetricTSPcomputesatourofcostatmost1:5timestheoptimum.1IntroductionTwodecadesofresearchfailedtoimproveuponChristo®des'algorithmf
8、ormetricTSP.Butsomere-searcherscontinuedtohopethatevenaPTASmightex-IntheTravelingSalesmanProblem(ªTSP"),weareg
此文档下载收益归作者所有