Geodesic
An asymptotically exact algorithm for the maximum-weight traveling salesman problem in a~finite-dimensional normed space
Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 4, pp. 84-91.

Voir la notice de l'article provenant de la source Math-Net.Ru

The algorithm generalizes the well-known A. Serdyukov's algorithm for the euclidean MAX TSP. The algorithm is asymptotically exact in the case of an arbitrary finite-dimensional normed space. Ill. 4, bibliogr. 6.
Keywords: MAX TSP, geometric traveling salesman problem, finite-dimensional normed space, asymptotically exact algorithm. 
@article{DA_2010_17_4_a5,
     author = {V. V. Shenmaier},
     title = {An asymptotically exact algorithm for the maximum-weight traveling salesman problem in a~finite-dimensional normed space},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {84--91},
     publisher = {mathdoc},
     volume = {17},
     number = {4},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2010_17_4_a5/}
}
TY  - JOUR
AU  - V. V. Shenmaier
TI  - An asymptotically exact algorithm for the maximum-weight traveling salesman problem in a~finite-dimensional normed space
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2010
SP  - 84
EP  - 91
VL  - 17
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2010_17_4_a5/
LA  - ru
ID  - DA_2010_17_4_a5
ER  - 
%0 Journal Article
%A V. V. Shenmaier
%T An asymptotically exact algorithm for the maximum-weight traveling salesman problem in a~finite-dimensional normed space
%J Diskretnyj analiz i issledovanie operacij
%D 2010
%P 84-91
%V 17
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2010_17_4_a5/
%G ru
%F DA_2010_17_4_a5
V. V. Shenmaier. An asymptotically exact algorithm for the maximum-weight traveling salesman problem in a~finite-dimensional normed space. Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 4, pp. 84-91. http://geodesic.mathdoc.fr/item/DA_2010_17_4_a5/

[1] Gimadi E. Kh., “Novaya versiya asimptoticheski-tochnogo algoritma resheniya evklidovoi zadachi kommivoyazhera na maksimum”, Tr. XII Baikalskoi mezhdunar. konferentsii, v. 1, Izd-vo ISEM SO RAN, Irkutsk, 2001, 117–123

[2] Serdyukov A. I., “Asimptoticheski tochnyi algoritm dlya zadachi kommivoyazhëra na maksimum v evklidovom prostranstve”, Metody tselochislennoi optimizatsii (Upravlyaemye sistemy), 27, Izd-vo in-ta matematiki, Novosibirsk, 1987, 79–87 | MR

[3] Serdyukov A. I., “Zadacha kommivoyazhëra na maksimum v konechnomernykh veschestvennykh prostranstvakh”, Diskret. analiz i issled. operatsii, 2:1 (1995), 50–56 | MR | Zbl

[4] Barvinok A. I., Johnson D. S., Woeginger G., Woodroofe R., “The maximum traveling salesman problem under polyhedral norms”, Integer Programming and Combinatorial Optimization, Lect. Notes Comput. Sci., 1412, Springer-Verl., Berlin, 1998, 195–201 | MR | Zbl

[5] Barvinok A. I., Fekete S. P., Johnson D. S., Tamir A., Woeginger G., Woodroofe R., “The geometric maximum traveling salesman problem”, J. ACM, 50:5 (2003), 641–664 | DOI | MR

[6] Fekete S. P., “Simplicity and hardness of the maximum traveling salesman problem under geometric distances”, Proc. 10th Ann. ACM-SIAM Symp. Discrete Algorithms, ACM, New York, 1999, 337–345 | MR | Zbl