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

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