Thumbnail

Approximation results toward nearest neighbor heuristic

Monnot, Jérôme (2002), Approximation results toward nearest neighbor heuristic, Yugoslav Journal of Operations Research, 12, 1, p. 11-16. http://dx.doi.org/10.2298/YJOR0201011M

View/Open
Type
Article accepté pour publication ou publié
Date
2002
Journal name
Yugoslav Journal of Operations Research
Volume
12
Number
1
Pages
11-16
Publication identifier
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc
Abstract (EN)
In this paper, we revisit the famous heuristic called nearest neighbor (NN) 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 Max TSP[a; ta] and a 2/(t + 1)-approximation for Min TSP[a; ta] under the standard performance ratio. Moreover, we show that these ratios are tight for some instances.
Subjects / Keywords
Traveling salesman problem; Analysis of algorithms; performance ratio; Approximate algorithms