A Near Optimal Approach for Symmetric Traveling Salesman Problem in Euclidean Space
文献类型：会议论文
| 作者 | Tian, Wenhong ; Huang, Chaojie; Wang, Xinyang
|
| 出版日期 | 2017 |
| 会议日期 | FEB 23-25, 2017 |
| 会议地点 | Porto, PORTUGAL |
| DOI | 10.5220/0006125202810287 |
| 页码 | 281-287 |
| 通讯作者 | Tian, WH (reprint author), Chinese Acad Sceinces, Chongqing Inst Green & Intelligent Technol, Chongqing, Peoples R China. ; Tian, WH (reprint author), Univ Elect Sci & Technol China, Sch Informat & Software Engn, Chengdu, Sichuan, Peoples R China. |
| 英文摘要 | The traveling salesman problem (TSP) is one of the most challenging NP-hard problems. It has widely applications in various disciplines such as physics, biology, computer science and so forth. The best known absolute (not asymptotic) approximation algorithm for Symmetric TSP (STSP) whose cost matrix satisfies the triangle inequality (called ASTSP) is Christofides algorithm which was proposed in 1976 and is a 3-approximation. Since then no proved improvement is made and improving upon this bound is a fundamental open question in combinatorial optimization. In this paper, for the first time, we propose Truncated Generalized Beta distribution (TGB) for the probability distribution of optimal tour lengths in a TSP. We then introduce an iterative TGB approach to obtain quality-proved near optimal approximation, i.e., (1+(alpha+1/alpha+2)(K-1))- approximation where K is the number of iterations in TGB and alpha(>>1) is the shape parameters of TGB. The result can approach the true optimum as K increases. |
| 会议录 | PROCEEDINGS OF THE 6TH INTERNATIONAL CONFERENCE ON OPERATIONS RESEARCH AND ENTERPRISE SYSTEMS (ICORES)
 |
| 语种 | 英语 |
| WOS记录号 | WOS:000413254200029 |
| 源URL | [http://119.78.100.138/handle/2HOD01W0/372]  |
| 专题 | 大数据挖掘及应用中心 |
| 作者单位 | (1) Chinese Acad Sceinces, Chongqing Inst Green & Intelligent Technol, Chongqing, Peoples R China; (2) Univ Elect Sci & Technol China, Sch Informat & Software Engn, Chengdu, Sichuan, Peoples R China |
| 推荐引用方式 GB/T 7714 | Tian, Wenhong,Huang, Chaojie,Wang, Xinyang. A Near Optimal Approach for Symmetric Traveling Salesman Problem in Euclidean Space[C]. 见:. Porto, PORTUGAL. FEB 23-25, 2017. |
入库方式： OAI收割
来源：重庆绿色智能技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。