Geodesic
Sufficient conditions of the stability of optimal route in the Travelling Salesman Problem in cases of a single vertex addition or substraction
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, no. 1 (2010), pp. 48-57 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The sufficient conditions for the stability of optimal travelling salesman route in case of the insertion of a new vertex between two consequent vertices and in case of the substraction of one vertex are deduced. Number of experiments, demonstrating stability areas and vertices are suggested for the Euclidean plane.
Keywords: travelling salesman problem, stability. 
@article{VUU_2010_1_a3,
     author = {E. E. Ivanko},
     title = {Sufficient conditions of the stability of optimal route in the {Travelling} {Salesman} {Problem} in cases of a~single vertex addition or substraction},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {48--57},
     year = {2010},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2010_1_a3/}
}
TY  - JOUR
AU  - E. E. Ivanko
TI  - Sufficient conditions of the stability of optimal route in the Travelling Salesman Problem in cases of a single vertex addition or substraction
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2010
SP  - 48
EP  - 57
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VUU_2010_1_a3/
LA  - ru
ID  - VUU_2010_1_a3
ER  - 
%0 Journal Article
%A E. E. Ivanko
%T Sufficient conditions of the stability of optimal route in the Travelling Salesman Problem in cases of a single vertex addition or substraction
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2010
%P 48-57
%N 1
%U http://geodesic.mathdoc.fr/item/VUU_2010_1_a3/
%G ru
%F VUU_2010_1_a3
E. E. Ivanko. Sufficient conditions of the stability of optimal route in the Travelling Salesman Problem in cases of a single vertex addition or substraction. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, no. 1 (2010), pp. 48-57. http://geodesic.mathdoc.fr/item/VUU_2010_1_a3/

[1] Gutin G., Punnen A. P., The Travelling Salesman Problem and Its Variations, Kluwer Academic Publishers, Dordrecht, 2007, 830 pp. | MR

[2] Chentsov A. G., Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii, Regulyarnaya i khaoticheskaya dinamika, Moskva, Izhevsk, 2008, 238 pp.

[3] Avner P. et al., “A Radiation Hybrid Transcript May of the Mouse Genome”, Nature Genetics, 29 (2001), 194–200 | DOI

[4] Agarwala R. et al., “A Fast and Scalable Radiation Hybrid Map Construction and Integration Strategy”, Genome Research, 10 (2000), 350–364 | DOI

[5] Baily C., McLain T., Beard R., “Fuel Saving Strategies for Separated Spacecraft Interferometry”, Proceedings of the AIAA Guidance, Navigation, and Control Conference (Denver, Colorado), 2000

[6] Poort E. S., Aspects of sensitivity analysis for the traveling salesman problem, PhD dissertation, University of Groningen, Groningen, 1997, 191 pp.

[7] Libura M., “Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems”, Discrete Applied Mathematics, 30:2–3 (1991), 197–211 | DOI | MR | Zbl

[8] Bokenhauer H.-J., Hromkovic J., Klasing R., Seibert S., Unger W., “Towards the Notion of Stability of Approximation for hard Optimization Tasks and the Traveling Salesman Problem”, Computer Science, 285 (1999), 3–24 | MR

[9] Buslaeva L. T., “Ob ustoichivosti algoritma “idi v blizhaishii””, Sb. nauchn. trudov Marshrutno-raspredelitelnye zadachi, UGTU-UPI, Ekaterinburg, 1995, 21–32