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 Transfer Statement
The copyright of this article is transferred to Current Applied Science and Technology journal with effect if and when the article is accepted for publication. The copyright transfer covers the exclusive right to reproduce and distribute the article, including reprints, translations, photographic reproductions, electronic form (offline, online) or any other reproductions of similar nature.
The author warrants 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.
Here is the link for download: Copyright transfer form.pdf
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.