期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

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

A Technique of Designing Approximation Schemes for NP-Hard Problems in Euclidean Space
下载PDF
导出
摘要 　　一、引言 　　欧氏空间中的组合优化问题均带有深远应用背景.这类问题的求解算法研究在计算机科学中占有重要位置.TSP问题、STEINER树问题、k-median 问题是三个经典的NP-Hard类组合优化问题[1～3],它们在欧氏平面上的求解算法广泛应用于网络可靠控制、集成电路设计、网络布局等领域.特别对TSP问题,虽然科学家们投入了大量的工作,但近三十年来没有取得实质性进展,而Arora等在1996-1998年应用相同的技术相继给出了上述问题在欧氏空间中的近似方案,使人们对该类问题的认识前进了一大步.……
作者 张洪良 朱大铭 马绍汉 王守强
出处 《计算机科学》 CSCD 北大核心 2002年第z1期117-119,共3页 Computer Science
分类号 TP3 [自动化与计算机技术—计算机科学与技术]
  • 相关文献

参考文献14

  • 1[1]Hochbaum D S. Approximation algorithms for NP-hard problems. PWS publishing company, 1997
  • 2[3]Motwant R,Raghavan P. Randomized Algorithms, ISBN : 0-521-47465-5,Cambridge University Press, 1995
  • 3[4]Arora S. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. In: Proc. of 37th IEEE Symposium on Foundations of Computer Science, 1996. 2～12
  • 4[5]Arora S. Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In:Proc. of 38th IEEE Symposium on Foundations of Computer Science, 1997. 554～ 563
  • 5[6]Rao S, Smith W D. Improved approximation for geometrical graphs via spanners and banyans. In: Proc. STOC, 1998. 540～550
  • 6[7]Arroa S, Raghavan P, Rao S. Approximation schemes for Euclidean k-medians and related problems. In:Proc. 30th Symp. Theory of Computing, ACM, May 1998. 106～113
  • 7[8]Kolliopoulos S G, Rao S. A Nearly Linear-Time Approximation Scheme for the Euclidean k-median Problem, 378-389, LNCS,1643, Springer, Berlin, 1999
  • 8[9]Sahni S,Gonzales T. p-complete approximation problems. J ACM ,1976,23:555～565
  • 9[10]Papadimitriou C H. Euclidean TSP is NP-Complete. Theriocal Computer Science, 1977,4: 237～244
  • 10[11]Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem. In: J. F. Traub, ed. Symposium on New Directions and Recent Results in Algorithms and Complexity, NY, Academic Press, 1976. 441
计算机科学
2002年 第z1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部