Worst Case Analyses of Nearest Neighbor Heuristic for Finding the Minimum Weight k - cycle
Article Sidebar
Main Article Content
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
Article Details
Copyright Agreement Statement
The corresponding author has to submit Copyright Agreement form after the article is accepted for publication in order to warrant that this contribution is original and that he/she has full power to make this grant. The author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors.
The author(s) grant Current Applied Science and Technology a non-exclusive, irrevocable, royalty-free license to publish, reproduce, distribute, and archive the article in print and electronic form with effect if and when the article is accepted for publication. In the event that the article is withdrawn prior to acceptance or is declined, this agreement shall have no effect, and no party shall be bound by it.
The author(s) retain copyright of this article, including but not limited to the right to reproduce and distribute the article, to include it in a thesis or book, and to post it on an institutional or personal repository, provided that the original publication in Current Applied Science and Technology is properly cited.
References
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.
Gutin, G., 2001. TSP tour domination and Hamilton cycle decomposition of regular digraphs. Operations Research Letters, 28, 107-111.
Gutin, G. Punnen, A. P. and Lenstra, J. K., 2002. The Traveling Salesman Problem and Its Variations. Boston: Kluwer Academic Publishers.
Nilsson, C., 2003. Heuristics for the traveling salesman problem. [online] Available at: http://160592857366.free.fr/joe/ebooks/ShareData/Heuristics%20for%20the%20Traveling%
Salesman%20Problem%20By%20Christian%20Nillson.pdf
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.
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.
Gutin, G. and Karapetyan, D., 2009. Generalized traveling salesman problem reduction algorithms. Algorithmic Operations Research, 4, 144-154.
Khachay, M. and Neznakhina, K., 2016. Approximability of the minimum-weight k -size cycle cover problem. Journal of Global Optimization, 66, 65-82.
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.
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.
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.
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.
