一种在欧氏空间设计多项式时间近似方案的新技术

作     者：张洪良 朱大铭 马绍汉 ZHANG Hong liang, ZHU Da ming & MA Shao han (School Of Computer Science And Technology, Shandong Univ., Jinan 250100, China)

作者机构：山东大学计算机科学与技术学院济南250100 

出 版 物：《山东大学学报（理学版）》 (Journal of Shandong University(Natural Science))

年 卷 期：2003年第38卷第2期

页      面：58-63页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金 (60 0 73 0 42 60 2 73 0 3 2 )资助项目 

主　　题：算法 多项式时间近似方案 复杂度 

摘      要：提出了一种在欧氏平面上设计多项式时间近似方案的新技术 .应用该技术设计多项式近似方案分为两步 :( 1)对欧氏平面进行随机分割 ;( 2 )对随机分割的结果利用动态规划技术计算近似最优解 .近年来Arora利用该技术获得了TSP ,Steiner树 ,K median三个著名NP hard问题的多项式近似方案 .经验表明 ,该技术适用于欧氏平面上对“距离和优化的NP hard问题 ,并可十分容易地推广到多维欧氏空间 .