Approximation result toward nearest neighbor heuristic
DOI:
https://doi.org/10.2298/YJOR0201011MKeywords:
Approximate algorithms, performance ratio, analysis of algorithms, traveling salesman problem.Abstract
In this paper, we revisit the famous heuristic called nearest neighbor (N N) for the traveling salesman problem under maximization and minimization goal. We deal with variants where the edge costs belong to interval Ša;taĆ for a>0 and t>1, which certainly corresponds to practical cases of these problems. We prove that NN is a (t+1)/2t-approximation for maxTSPŠa;taĆ and a 2/(t+1)-approximation for minTSPŠa;taĆ under the standard performance ratio. Moreover, we show that these ratios are tight for some instances.References
Arora, S. (1996) Polynomial time approximation schemes for Euclidean TSP and other geometric problems. u: FOCS'96, Proc, str. 2-11
Christofides, N. (1976) Worst-case analysis of a new heuristic for the traveling salesman problem. u: Technical report, Grad. School of Industrial Administration, CMU, 338
Engebretsen, L., Karpinski, M. (2000) Approximation hardness of TSP with bounded matrices. u: E.C.C.C. Report TR00-089
Fisher, M.I., Nemhauser, G.L., Wolsey, L.A. (1979) An analysis of approximations for finding a maximum weight Hamiltonian circuit. Operations Research, 27, 4, 799-809
Karg, L.L., Thompson, G.L. (1964) A heuristic approach to traveling salesman problems. Management Science, 10, 225-248
Papadimitriou, C.H., Vempala, S. (2000) On the approximability of the traveling salesman problem. u: Proc. S.T.O.C. 2000
Papadimitriou, C.H., Yannakakis, M. (1993) The traveling salesman problem with distances one and two. Mathematics of Operations Research, 18, 1, 1-11
Rosenkrantz, D.J., Stearns, R.E., Lewis, P.M. (1977) An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6, 3, 563-581
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.