WIN algorithm for discrete online TSP
Article
Article Title | WIN algorithm for discrete online TSP |
---|---|
ERA Journal ID | 40120 |
Article Category | Article |
Authors | Wu, Yonghua (Author), Zhu, Guohun (Author), Chen, Huaying (Author) and Qin, Jucun (Author) |
Journal Title | Journal of Advanced Computational Intelligence and Intelligent Informatics |
Journal Citation | 15 (9), pp. 1199-1202 |
Number of Pages | 4 |
Year | 2011 |
Place of Publication | Tokyo, Japan |
ISSN | 1343-0130 |
1883-8014 | |
Web Address (URL) | http://www.fujipress.jp/JACIII/JACII00150009.html#no_150901 |
Abstract | Traveling Salesman Problem (TSP) which is proved as an NP-Complete problem is solved by many algorithms. In this paper, we propose online TSP which is based on general discrete metric space. A Waiting- If-Necessary (WIN) algorithm is proposed that involves with increasing cost caused by zealous algorithms and unnecessary waiting caused by cautious algorithms. We measure the performance of the WIN algorithm using competitive analysis and found that it is a 2-competitive algorithm. The competitive ratio of theWIN algorithm can be improved by setting parameter T0. |
Keywords | competitive analysis; discrete metric space; metric TSP; online TSP; waiting-if-necessary |
ANZSRC Field of Research 2020 | 460699. Distributed computing and systems software not elsewhere classified |
490304. Optimisation | |
490404. Combinatorics and discrete mathematics (excl. physical combinatorics) | |
Public Notes | Files associated with this item cannot be displayed due to copyright restrictions. |
Byline Affiliations | Guilin University of Electronic Technology, China |
Department of Mathematics and Computing | |
University of Melbourne | |
Institution of Origin | University of Southern Queensland |
https://research.usq.edu.au/item/q1486/win-algorithm-for-discrete-online-tsp
1950
total views11
total downloads0
views this month0
downloads this month