
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
Voir/Ouvrir
Type
Article accepté pour publication ou publiéDate
2002Nom de la revue
Yugoslav Journal of Operations ResearchVolume
12Numéro
1Pages
11-16
Identifiant publication
Métadonnées
Afficher la notice complèteRésumé (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.Mots-clés
Traveling salesman problem; Analysis of algorithms; performance ratio; Approximate algorithmsPublications associées
Affichage des éléments liés par titre et auteur.
-
Monnot, Jérôme; Demange, Marc; Paschos, Vangelis (2003) Article accepté pour publication ou publié
-
Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence
-
Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié
-
Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Communication / Conférence
-
Monnot, Jérôme (2002) Article accepté pour publication ou publié