Geodesic
Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 14 (2008) no. 2, pp. 23-32 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The paper presents a polynomial approximation algorithm $\mathcal A$ solving the problem of finding one and two edge-disjoint Hamiltonian cycles (traveling salesman routes) of maximal weight in a complete weighted undirected graph in multidimensional Euclidean space. The asymptotic optimality of the algorithm is established. 
@article{TIMM_2008_14_2_a3,
     author = {E. Kh. Gimadi},
     title = {Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in {Euclidean} space},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {23--32},
     year = {2008},
     volume = {14},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2008_14_2_a3/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
TI  - Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2008
SP  - 23
EP  - 32
VL  - 14
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2008_14_2_a3/
LA  - ru
ID  - TIMM_2008_14_2_a3
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%T Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
%J Trudy Instituta matematiki i mehaniki
%D 2008
%P 23-32
%V 14
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2008_14_2_a3/
%G ru
%F TIMM_2008_14_2_a3
E. Kh. Gimadi. Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 14 (2008) no. 2, pp. 23-32. http://geodesic.mathdoc.fr/item/TIMM_2008_14_2_a3/

[1] Serdyukov A. I., “Asimptoticheski tochnyi algoritm dlya zadachi kommivoyazhera na maksimum v evklidovom prostranstve”, Metody tselochislennoi optimizatsii (Upravlyaemye sistemy), 27, Novosibirsk, 1987, 79–87 | MR | Zbl

[2] Gimadi E. Kh., “Novaya versiya asimptoticheski tochnogo algoritma resheniya evklidovoi zadachi kommivoyazhera”, Metody optimizatsii i ikh prilozheniya, Tr. XII Baikalskoi mezhdunar. konf. T. 1, Irkutsk, 2001, 117–124

[3] Baburin A. E., Gimadi E. Kh., “Ob asimptoticheskoi tochnosti odnogo algoritma resheniya zadachi kommivoyazhera na maksimum v evklidovom prostranstve”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 9:4 (2002), 23–32, Novosibirsk | MR | Zbl

[4] Barvinok A. A., Gimadi E. Kh., and Serdyukov A. I., “The maximum TSP”, The traveling salesman problem and its variations, eds. A. Punnen and G. Gutin, Kluwer Acad. Publ., Dordrecht, 2002, 585–608 | MR

[5] Fekete S. P., Simplicity and hardness of the maximum traveling salesman problem under geometric distances, Tech. Rep. 98.329, Center for Applied Computer Science, Köln, 2006

[6] Gabow H. N., “An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems”, Proc. of the 15th annual ACM symposium on theory of computing, ACM, New York, 1983, 448–456

[7] Baburin A. E., Gimadi E. Kh., “Certain generalization of the maximum traveling salesman problem”, J. of Appl. and Industr. Mathematics, 1:4 (2007), 418–423 | DOI | MR