| 一种在欧氏空间设计多项式时间近似方案的新技术 |
| |
| 引用本文： | 张洪良,朱大铭,马绍汉.一种在欧氏空间设计多项式时间近似方案的新技术[J].山东大学学报(理学版),2003,38(2):58-63. |
| |
| 作者姓名： | 张洪良 朱大铭 马绍汉 |
| |
| 作者单位： | 山东大学,计算机科学与技术学院,济南,250100 |
| |
| 基金项目： | 国家自然科学基金 (60 0 73 0 42 ,60 2 73 0 3 2 )资助项目 |
| |
| 摘 要： | 提出了一种在欧氏平面上设计多项式时间近似方案的新技术．应用该技术设计多项式近似方案分为两步：(1)对欧氏平面进行随机分割；(2)对随机分割的结果利用动态规划技术计算近似最优解．近年来Arora利用该技术获得了TSP，Steiner树，K-median三个著名NP-hard问题的多项式近似方案．经验表明，该技术适用于欧氏平面上对“距离和”优化的NP-hard问题，并可十分容易地推广到多维欧氏空间．
|
| 关 键 词： | 算法 多项式时间近似方案 复杂度 |
| 文章编号： | 1671-9352(2003)02-0058-06 |
| 修稿时间： | 2002年10月22 |
A New Technique to Design Polynomial Time Approximation Schemes in Euclidean Space |
| |
| ZHANG Hong liang,ZHU Da ming & MA Shao han.A New Technique to Design Polynomial Time Approximation Schemes in Euclidean Space[J].Journal of Shandong University,2003,38(2):58-63. |
| |
| Authors: | ZHANG Hong liang ZHU Da ming & MA Shao han |
| |
| Abstract: | A new technique to design polynomial time approximation schemes(PTAS) for NP hard problems in Euclidean space is introduced. The design for PTAS includes two steps: first, partitioning the Euclidean plane with a randomized method; second, seeking the approximation solution with dynamic programming approach in the partitioned plane. In recent years, having used this technique, Arora has given PTAS for TSP, Steiner Tree and K median. This method can be widely used on combinatorial optimization problems in Euclidean space with the sum of some Euclidean distances as optimization objectives, and can be easily extended to Euclidean space of more than two dimensions. |
| |
| Keywords: | algorithms PTAS complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
