|
|||||
|
|
| 一种在欧氏空间设计多项式时间近似方案的新技术 | |
| 作者姓名： | 张洪良 朱大铭 马绍汉 |
| 摘 要： | 提出了一种在欧氏平面上设计多项式时间近似方案的新技术．应用该技术设计多项式近似方案分为两步：(1)对欧氏平面进行随机分割；(2)对随机分割的结果利用动态规划技术计算近似最优解．近年来Arora利用该技术获得了TSP，Steiner树，K-median三个著名NP—hard问题的多项式近似方案．经验表明，该技术适用于欧氏平面上对“距离和”优化的NP—hard问题，并可十分容易地推广到多维欧氏空间． |
| 关 键 词： | 算法 多项式时间近似方案 复杂度 |
| 本文献已被 维普 等数据库收录！ | |