Geodesic
An approximation algorithm for the maximum traveling salesman problem
Journal of computational and engineering mathematics, Tome 4 (2017) no. 3, pp. 49-54 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The question considered in the travelling salesman problem is the following. For a given list of cities and the distances between each pair of cities, to construct the shortest possible path that visits each city exactly once and returns to the origin city. The problem is an NP-hard problem in combinatorial optimization and is important in operations research. The traveling salesman problem is one of the most famous and heavily researched problems in theoretical computer science. We consider the version, which is the Symmetric Maximum Traveling Salesman Problem. The article describes an approximation algorithm for the maximum traveling salesman problem, based on two known polynomial time approximation algorithms. The accuracy of this algorithm is 25/33.
Keywords: Hamiltonian cycle, traveling salesman problem, approximation algorithm, cycle cover, matching, accuracy of solution. 
@article{JCEM_2017_4_3_a5,
     author = {A. Yu. Evnin and N. I. Yusova},
     title = {An approximation algorithm for the maximum traveling salesman problem},
     journal = {Journal of computational and engineering mathematics},
     pages = {49--54},
     year = {2017},
     volume = {4},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JCEM_2017_4_3_a5/}
}
TY  - JOUR
AU  - A. Yu. Evnin
AU  - N. I. Yusova
TI  - An approximation algorithm for the maximum traveling salesman problem
JO  - Journal of computational and engineering mathematics
PY  - 2017
SP  - 49
EP  - 54
VL  - 4
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/JCEM_2017_4_3_a5/
LA  - en
ID  - JCEM_2017_4_3_a5
ER  - 
%0 Journal Article
%A A. Yu. Evnin
%A N. I. Yusova
%T An approximation algorithm for the maximum traveling salesman problem
%J Journal of computational and engineering mathematics
%D 2017
%P 49-54
%V 4
%N 3
%U http://geodesic.mathdoc.fr/item/JCEM_2017_4_3_a5/
%G en
%F JCEM_2017_4_3_a5
A. Yu. Evnin; N. I. Yusova. An approximation algorithm for the maximum traveling salesman problem. Journal of computational and engineering mathematics, Tome 4 (2017) no. 3, pp. 49-54. http://geodesic.mathdoc.fr/item/JCEM_2017_4_3_a5/

[1] A. I. Barvinok, D. S. Johnson, G. J. Woeginger, R. Woodroofe, “The Maximum Traveling Salesman Problem Under Polyhedral Norms”, IPCO VI LNCS, 1412 (1998), 195–201 | DOI | MR | Zbl

[2] R. Hassin, S. Rubinstein, “An Approximation Algorithm for the Maximum Traveling Salesman Problem”, Information Processing Letters, 67:3 (1998), 125–130 | DOI | MR | Zbl

[3] A. I. Serdyukov, “Algoritm s otsenkoi dlya zadachi kommivoyazhera na maksimum”, Upravlyaemye sistemy, 25 (1984), 80–86 | MR | Zbl

[4] A. V. Kostochka, A. I. Serdyukov, “Polinomialnye algoritmy s otsenkami 3/4 i 5/6 dlya zadachi kommivoyazhera na maksimum”, Upravlyaemye sistemy, 26 (1985), 55–59

[5] G. Gutin, A. P. Punnen, The Traveling Salesman Problem and Its Variations, Kluwer Academic Publishers, Boston–Dordrecht–London, 2002 | MR | Zbl