WIN Algorithm for Discrete Online TSP
Yonghua Wu*, Guohun Zhu*,**, Huaying Chen***,
and Jucun Qin*
*School of Computer Science and Engineering, Guilin University of Electronic Technology, No.1 Jinji Road, Guilin 541004, China
**Department of Math and Computer, University of Southern Queensland, Toowoomba, QLD, Australia
***Graduate School of Science, Department of Information System, University of Melbourne, Melbourne, Australia
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.
-  G. Laporte, “A concise guide to the Traveling Salesman Problem,” J. of the Operational Research Society, Vol.61, pp. 35-40, 2010.
-  Y. Wu, G. Zhu, and T. Sang, “On Update Mechanism of Online Traveling Salesman Problems,” 2010 Int. Conf. on Intelligent Computing and Integrated Systems, pp. 53-56, 2010.
-  K. Zhou et al., “Algorithms for TSP,” Computer Engineering and Applications, Vol.43, No.29, pp. 43-47, 2007.
-  G. Ausiello et al., “Online Algorithms, Real time, the Virtue of Laziness, and the Power of Clairvoyance,” TAMC, pp. 1-20, 2006.
-  G. Ausiello et al., “Algorithms for the Online Quota Traveling Salesman Problem,” Information processing Letters, Vol.92, pp. 89-94, 2004.
-  G. Ausiello, E. Feuerstein, S. Leonardi, et al., “Algorithms for the Online Traveling Salesman,” Algorithmica, Vol.29, pp. 560-581, 2001.
-  M. Aprea et al., “Discrete Online TSP,” AAIM 2009, LNCS 5564, pp. 29-42, 2009.
-  V. Bonifaci, “Models and algorithms for online sever routing,” Ph.D. Thesis, Technische Universiteit Eindhoven, 2007.
-  P. Jaillet and M. R. Wagner, “Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses,” Operations Research, Vol.56, No.3, pp. 745-757, 2008.
-  V. Bonifaci, “An adversarial queueing model for online sever routing,” Theoretical Computer Science, Vol.381, pp. 280-287, 2007.
-  V. Bonifaci and L. Stougie, “Online k-Sever Routing Problems,” Theory Comput Syst, Vol.45, pp. 470-485, 2009.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.