欧氏平面上NP-hard优化问题多项式时间近似方案设计技术  

A Technique of Designing Approximation Schemes for NP-Hard Problems in Euclidean Space

作　　者：张洪良 朱大铭 马绍汉 王守强 

出　　处：《计算机科学》2002年第z1期117-119,共3页Computer Science

摘　　要：　　一、引言 　　欧氏空间中的组合优化问题均带有深远应用背景.这类问题的求解算法研究在计算机科学中占有重要位置.TSP问题、STEINER树问题、k-median 问题是三个经典的NP-Hard类组合优化问题[1～3],它们在欧氏平面上的求解算法广泛应用于网络可靠控制、集成电路设计、网络布局等领域.特别对TSP问题,虽然科学家们投入了大量的工作,但近三十年来没有取得实质性进展,而Arora等在1996-1998年应用相同的技术相继给出了上述问题在欧氏空间中的近似方案,使人们对该类问题的认识前进了一大步.……

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]