A Near Optimal Approach for Symmetric Traveling Salesman Problem in Euclidean Space
Wenhong Tian, Chaojie Huang, Xinyang Wang
2017
Abstract
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 approximation algorithm for Symmetric TSP (STSP) whose cost matrix satisfies the triangle inequality (called ?STSP) is Christofides algorithm which was proposed in 1976 and is a 3/2 approximation. Since then no proved improvement is made and improving upon this bound is a funda- mental open question in combinatorial optimization. In this paper, for the first time, we propose Trun- cated 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+1/2((a+1)/(a+2))^(K-1))-approximation where K is the number of iterations in TGB and a(>> 1) is the shape parameters of TGB. The result can approach the true optimum as K increases.
DownloadPaper Citation
in Harvard Style
Tian W., Huang C. and Wang X. (2017). A Near Optimal Approach for Symmetric Traveling Salesman Problem in Euclidean Space . In Proceedings of the 6th International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES, ISBN 978-989-758-218-9, pages 281-287. DOI: 10.5220/0006125202810287
in Bibtex Style
@conference{icores17,
author={Wenhong Tian and Chaojie Huang and Xinyang Wang},
title={A Near Optimal Approach for Symmetric Traveling Salesman Problem in Euclidean Space},
booktitle={Proceedings of the 6th International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES,},
year={2017},
pages={281-287},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0006125202810287},
isbn={978-989-758-218-9},
}
in EndNote Style
TY - CONF
JO - Proceedings of the 6th International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES,
TI - A Near Optimal Approach for Symmetric Traveling Salesman Problem in Euclidean Space
SN - 978-989-758-218-9
AU - Tian W.
AU - Huang C.
AU - Wang X.
PY - 2017
SP - 281
EP - 287
DO - 10.5220/0006125202810287