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
TypeArticle accepté pour publication ou publié
Journal nameYugoslav Journal of Operations Research
MetadataShow full item record
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 / KeywordsTraveling salesman problem; Analysis of algorithms; performance ratio; Approximate algorithms
Showing items related by title and author.
Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié