Geodesic
On the asymptotic accuracy of an algorithm for solving the $m$-PSP maximum problem in a multidimensional Euclidean space
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 3, pp. 12-24
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

An efficient algorithm $\mathcal A$ with a guaranteed accuracy estimate is presented for solving the problem of finding several edge-disjoint Hamiltonian circuits (traveling salesman routes) of maximal weight in a complete weighted undirected graph in a multidimensional Euclidean space $\mathbb R^k$. The complexity of the algorithm is $O(n^3)$. The number of traveling salesman routes for which the algorithm is asymptotically exact is established.
Keywords: maximum traveling salesman problem, edge-disjoint Hamiltonian circuits, asymptotic accuracy, multidimensional Euclidean space.
Mots-clés : polynomial algorithm 
@article{TIMM_2010_16_3_a1,
     author = {A. E. Baburin and E. Kh. Gimadi},
     title = {On the asymptotic accuracy of an algorithm for solving the $m${-PSP} maximum problem in a~multidimensional {Euclidean} space},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {12--24},
     year = {2010},
     volume = {16},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a1/}
}
TY  - JOUR
AU  - A. E. Baburin
AU  - E. Kh. Gimadi
TI  - On the asymptotic accuracy of an algorithm for solving the $m$-PSP maximum problem in a multidimensional Euclidean space
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2010
SP  - 12
EP  - 24
VL  - 16
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a1/
LA  - ru
ID  - TIMM_2010_16_3_a1
ER  - 
%0 Journal Article
%A A. E. Baburin
%A E. Kh. Gimadi
%T On the asymptotic accuracy of an algorithm for solving the $m$-PSP maximum problem in a multidimensional Euclidean space
%J Trudy Instituta matematiki i mehaniki
%D 2010
%P 12-24
%V 16
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a1/
%G ru
%F TIMM_2010_16_3_a1
A. E. Baburin; E. Kh. Gimadi. On the asymptotic accuracy of an algorithm for solving the $m$-PSP maximum problem in a multidimensional Euclidean space. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 3, pp. 12-24. http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a1/

[1] Ageev A. A., Baburin A. E., Gimadi E. Kh., “Polinomialnyi algoritm s otsenkoi 3/4 dlya nakhozhdeniya dvukh reberno-neperesekayuschikhsya gamiltonovykh tsiklov maksimalnogo summarnogo vesa”, Diskret. analiz i issled. operatsii. Ser. 1, 13:2 (2006), 11–20 | MR

[2] Ageev A. A., Pyatkin A. V., “Priblizhennyi algoritm resheniya metricheskoi zadachi o dvukh kommivoyazherakh s otsenkoi tochnosti 2”, Diskret. analiz i issled. operatsii, 16:4 (2009), 3–20 | MR

[3] Baburin A. E., Gimadi E. Kh., Korkishko N. M., “Priblizhennye algoritmy dlya nakhozhdeniya dvukh reberno-neperesekayuschikhsya gamiltonovykh tsiklov minimalnogo summarnogo vesa”, Diskret. analiz i issled. operatsii. Ser. 2, 11:1 (2004), 11–25 | MR | Zbl

[4] Baburin A. E., Gimadi E. Kh., “Ob odnom obobschenii zadachi kommivoyazhera na maksimum”, Diskret. analiz i issled. operatsii. Ser. 1, 13:3 (2006), 3–12 | MR

[5] Gimadi E. Kh., Glazkov Yu. V., Glebov A. N., “Priblizhennye algoritmy resheniya zadachi o dvukh kommivoyazherakh v polnom grafe s vesami reber 1 i 2”, Diskret. analiz i issled. operatsii. Ser. 2, 14:2 (2007), 41–61 | MR

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

[7] Gimadi E. Kh., “Asimptoticheski tochnyi algoritm otyskaniya odnogo i dvukh reberno-neperesekayuschikhsya marshrutov kommivoyazhera maksimalnogo vesa v evklidovykh prostranstvakh”, Tr. In-ta matematiki i mekhaniki UrO RAN, 14, no. 2, 2008, 23–32 | Zbl

[8] Emelichev V. A. [i dr.], Lektsii po teorii grafov, Nauka, M., 1990, 384 pp. | MR | Zbl

[9] Ore O., Teoriya grafov, 2-e izd., Nauka, M., 1980, 336 pp. | MR

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

[11] Baburin A. E., Croce F., Gimadi E. Kh., Glazkov Y. V., Paschos V., “Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2”, Discrete Appl. Math., 157:9 (2009), 1988–1992 | DOI | MR | Zbl

[12] Gabow H. N., “An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems”, Proc. 15th annual ACM simposium on theory of computing (Boston, USA, Apr. 25–27, 1983), ACM, New York, 1983, 448–456

[13] Hopcroft J. E., Karp R. M., “An $n^{5/2}$-algorithm for maximum matchings in bipartite graphs”, SIAM J. Comp., 2 (1973), 225–231 | DOI | MR | Zbl

[14] De Kort J. B. J. M., “A branch and bound algorithm for symmetric-peripatetic salesman problems”, European J. Oper. Research, 70 (1993), 229–243 | DOI | Zbl

[15] De Kort J. B. J. M., “Lower bounds for symmetric $K$-peripatetic salesman problems”, Optimization, 22:1 (1991), 113–122 | DOI | MR | Zbl

[16] Krarup J., “The peripatetic salesman and some related unsolved problems”, Combinatorial programming:methods and applications, Proc. NATO Advanced Study Inst. Versailles, 1974, 173–178 | MR

[17] E. L. Lawler [et al.] (eds.), The traveling salesman problem: A guided tour of combinatorial optimization, Wiley, Chichester, 1985, 476 pp. | MR | Zbl

[18] G. Gutin, A. P. Punnen (eds.), The traveling salesman problem and its variations, Kluver Acad. Publ., Dordrecht–Boston–London, 2002, 826 pp. | MR

[19] Wolfter C. R., Cordone R., “A heuristic approach to the overnight security service problem”, Comput. Oper. Research, 30:9 (2003), 1269–1287 | DOI