In:
Journal of Advanced Computational Intelligence and Intelligent Informatics, Fuji Technology Press Ltd., Vol. 15, No. 9 ( 2011-11-20), p. 1199-1202
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 T 0 .
Type of Medium:
Online Resource
ISSN:
1883-8014
,
1343-0130
DOI:
10.20965/jaciii.2011.p1199
Language:
English
Publisher:
Fuji Technology Press Ltd.
Publication Date:
2011
detail.hit.zdb_id:
2740249-6
detail.hit.zdb_id:
2708994-0
Permalink