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., "Polynomial time approximation scheme for Euclidean TSP and other geometric problems", Proc. F.O.C.S., 1996, 2-11.
Christofides, N., "Worst-case analysis of a new heuristic for the traveling salesman problem", Technical report 338, Grad. School of Industrial Administration, CMU, 1976.
Engebretsen, L., and Karpinski, M., "Approximation hardness of TSP with bounded matrices", E.C.C.C. Report TR00-089, 2000.
Fisher, M.I., Nemhauser, G.L., and Wolsey, L.A., "An analysis of approximations for finding a maximum weight Hamiltonian circuit", Op. Res., 27 (4) (1979) 799-809.
Karg, L.L., and Thompson, G.L., "A heuristic approach to traveling salesman problems", Management Sci., 10 (1964) 225-248.
Papadimitriou, C.H., and Vempala, S., "On the approximability of the traveling salesman problem", Proc. S.T.O.C. 2000, 2000.
Papadimitriou, C.H., and Yannakakis, M., "The traveling salesman problem with distance one and two", Math. Oper. Res., 18 (1993) 1-11.
Rosenkrantz, D.J., Stearns, R.E., and Lewis, P.M., "An analysis of several heuristics for the traveling salesman problem", S.I.A.M. J. Comp., 6 (1977) 563-581.
Downloads
Published
Issue
Section
License
Copyright (c) 2002 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
