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