中国科学院重庆绿色智能技术研究院机构知识库

QQ客服 官方微博 反馈留言

	A Near Optimal Approach for Symmetric Traveling Salesman Problem in Euclidean Space
	Tian, Wenhong; Huang, Chaojie; Wang, Xinyang
	2017
摘要	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.
语种	英语
DOI	10.5220/0006125202810287
会议(录)名称	PROCEEDINGS OF THE 6TH INTERNATIONAL CONFERENCE ON OPERATIONS RESEARCH AND ENTERPRISE SYSTEMS (ICORES)
页码	281-287
收录类别	EI
会议地点	Porto, PORTUGAL
会议日期	FEB 23-25, 2017