Worst Case Analyses of Nearest Neighbor Heuristic for Finding the Minimum Weight k - cycle

Main Article Content

Tanapat Chalarux
Piyashat Sripratak*

Abstract

Given a weighted complete graph ( Kn, w), where w is an edge weight function, the minimum weight k - cycle problem is to find a cycle of k vertices whose total weight is minimum among all k - cycles. Traveling salesman problem (TSP) is a special case of this problem when k = n. Nearest neighbor algorithm (NN) is a popular greedy heuristic for TSP that can be applied to this problem. To analyze the worst case of the NN for the minimum weight k - cycle problem, we prove that it is impossible for the NN to have an approximation ratio. An instance of the minimum weight k - cycle problem is given, in which the NN finds a k - cycle whose weight is worse than the average value of the weights of all k - cycles in that instance. Moreover, the domination number of the NN when k = n and its upper bound for the case k = n – 1 is established.


 


Keywords: minimum weight k - cycle; worst case analysis; nearest neighbor heuristic

*Corresponding author: Tel.: +66 61 267 6777


                                           E-mail: psripratak@gmail.com

Downloads

Download data is not yet available.

Article Details

Section
Research Articles

References

[1] Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G. and Shmoys, D.B., 1985. The Traveling Salesman Problem. Chichester: John Wiley and Sons Ltd.
[2] Gutin, G., 2001. TSP tour domination and Hamilton cycle decomposition of regular digraphs. Operations Research Letters, 28, 107-111.
[3] Gutin, G. Punnen, A. P. and Lenstra, J. K., 2002. The Traveling Salesman Problem and Its Variations. Boston: Kluwer Academic Publishers.
[4] Nilsson, C., 2003. Heuristics for the traveling salesman problem. [online] Available at: http://160592857366.free.fr/joe/ebooks/ShareData/Heuristics%20for%20the%20Traveling%
20Salesman%20Problem%20By%20Christian%20Nillson.pdf
[5] Khan, A.A. and Agrawala, H., 2016. Comparative study of nearest neighbour algorithm and genetic algorithm in solving traveling salesman problem. International Research Journal of Engineering and Technology, 3, 234-238.
[6] Wu, Y., Weise, T. and Chiong, R., 2015. Local search for the traveling salesman problem: a comparative study. Proceedings of IEEE 14th International Conference on Cognitive Informatics and Cognitive Computing, 213-220.
[7] Gutin, G. and Karapetyan, D., 2009. Generalized traveling salesman problem reduction algorithms. Algorithmic Operations Research, 4, 144-154.
[8] Khachay, M. and Neznakhina, K., 2016. Approximability of the minimum-weight k -size cycle cover problem. Journal of Global Optimization, 66, 65-82.
[9] Gutin, G., Yeob, A. and Zverovich, A., 2002. Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics, 117, 81-86.
[10] Brecklinghaus, J. and Hougardy, S., 2015. The approximation ratio of the greedy algorithm for the metric traveling salesman problem. Operations Research Letters, 43, 259-261.
[11] Punnen, A.P., Sripratak, P. and Karapetyan, D., 2015. Average value of solutions for the bipartite boolean quadratic programs and rounding algorithms. Theoretical Computer Science, 565, 77-89.
[12] Glover, F. and Punnen, A.P., 1997. The traveling salesman problem: new solvable cases and linkages with the development of approximation algorithms. Journal of the Operational Research Society, 48, 502-510.