Geodesic
Approximation Results Toward Nearest Neighbor Heuristic
Yugoslav journal of operations research, Tome 12 (2002) no. 1, p. 11 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

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 $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.
Classification : 90C59 90C27
Keywords: Approximate algorithms, performance ratio, analysis of algorithms, traveling salesman problem. 
@article{YJOR_2002_12_1_a1,
     author = {J\'er\^ome Monnot},
     title = {Approximation {Results} {Toward} {Nearest} {Neighbor} {Heuristic}},
     journal = {Yugoslav journal of operations research},
     pages = {11 },
     year = {2002},
     volume = {12},
     number = {1},
     zbl = {1045.90089},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2002_12_1_a1/}
}
TY  - JOUR
AU  - Jérôme Monnot
TI  - Approximation Results Toward Nearest Neighbor Heuristic
JO  - Yugoslav journal of operations research
PY  - 2002
SP  - 11 
VL  - 12
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/YJOR_2002_12_1_a1/
LA  - en
ID  - YJOR_2002_12_1_a1
ER  - 
%0 Journal Article
%A Jérôme Monnot
%T Approximation Results Toward Nearest Neighbor Heuristic
%J Yugoslav journal of operations research
%D 2002
%P 11 
%V 12
%N 1
%U http://geodesic.mathdoc.fr/item/YJOR_2002_12_1_a1/
%G en
%F YJOR_2002_12_1_a1
Jérôme Monnot. Approximation Results Toward Nearest Neighbor Heuristic. Yugoslav journal of operations research, Tome 12 (2002) no. 1, p. 11 . http://geodesic.mathdoc.fr/item/YJOR_2002_12_1_a1/