ENRU
English version: Journal of Applied and Industrial Mathematics, 2017, 11:3, 354361 

Volume 24, No 3, 2017, P. 519 UDC 519.8
Keywords: $m$Peripatetic Salesman Problem, asymptotically optimal algorithm, random inputs, discrete distribution. DOI: 10.17377/daio.2017.24.551 Edward Kh. Gimadi ^{1,2} Received 3 August 2016 References[1] A. A. Ageev, A. E. Baburin, and E. Kh. Gimadi, A 3/4approximation algorithm for finding two disjoint Hamiltonian cycles of maximum weight, Diskretn. Anal. Issled. Oper., Ser. 1, 13, No. 2, 11–20, 2006 [Russian]. Translated in J. Appl. Ind. Math., 1, No. 2, 142–147, 2007.[2] A. A. Ageev and A. V. Pyatkin, A 2approximation algorithm for the metric 2peripatetic salesman problem, Diskretn. Anal. Issled. Oper., 16, No. 4, 3–20, 2009 [Russian]. [3] A. E. Baburin and E. Kh. Gimadi, On the asymptotic optimality of an algorithm for solving the maximum $m$PSP in a multidimensional Euclidean space, Tr. Inst. Mat. Mekh., 16, No. 3, 12–24, 2010 [Russian]. Translated in Proc. Steklov Inst. Math., 272, Suppl. 1, S1–S13, 2011. [4] A. E. Baburin, E. Kh. Gimadi, and N. M. Korkishko, Approximation algorithms for finding two edgedisjoint Hamiltonian cycles of minimal total weight, Diskretn. Anal. Issled. Oper., Ser. 2, 11, No. 1, 11–25, 2004 [Russian]. [5] E. Kh. Gimadi, Yu. V. Glazkov, and A. N. Glebov, Approximation algorithms for solving the 2peripatetic salesman problem on a complete graph with edge weights 1 and 2, Diskretn. Anal. Issled. Oper., Ser. 2, 14, No. 2, 41–61, 2007 [Russian]. Translated in J. Appl. Ind. Math., 3, No. 1, 46–60, 2009. [6] E. Kh. Gimadi, Yu. V. Glazkov, and O. Yu. Tsidulko, The probabilistic analysis of an algorithm for solving the $m$planar 3dimensional assignment problem on onecycle permutations, Diskretn. Anal. Issled. Oper., 21, No. 1, 15–29, 2014 [Russian]. Translated in J. Appl. Ind. Math., 8, No. 2, 208–217, 2014. [7] E. Kh. Gimadi, A. M. Istomin, I. A. Rykov, and O. Yu. Tsidulko, Probabilistic analysis of an approximation algorithm for the $m$peripatetic salesman problem on random instances unbounded from above, Tr. Inst. Mat. Mekh., 20, No. 2, 88–98, 2014 [Russian]. Translated in Proc. Steklov Inst. Math., 289, Suppl. 1, S77–S87, 2015. [8] E. Kh. Gimadi and E. V. Ivonina, Approximation algorithms for the maximum 2peripatetic salesman problem, Diskretn. Anal. Issled. Oper., 19, No. 1, 17–32, 2012 [Russian]. Translated in J. Appl. Ind. Math., 6, No. 3, 295–305, 2012. [9] E. Kh. Gimadi and V. A. Perepelitsa, A statistically effective algorithm for selection of a Hamiltonian contour or cycle, in Diskretnyi analiz (Discrete Analysis), Vol. 22, pp. 15–28, Inst. Mat. SO AN SSSR, Novosibirsk, 1973 [Russian]. [10] A. N. Glebov and D. Zh. Zambalaeva, A polynomial algorithm with approximation ratio 7/9 for the maximum two peripatetic salesmen problem, Diskretn. Anal. Issled. Oper., 18, No. 4, 17–48, 2011 [Russian]. Translated in J. Appl. Ind. Math., 6, No. 1, 69–89, 2012. [11] A. N. Glebov and D. Zh. Zambalaeva, An approximation algorithm for the minimum two peripatetic salesmen problem with different weight functions, Diskretn. Anal. Issled. Oper., 18, No. 5, 11–37, 2011 [Russian]. Translated in J. Appl. Ind. Math., 6, No. 2, 167–183, 2012. [12] A. D. Korshunov, On the power of some classes of graphs, Dokl. Akad. Nauk SSSR, 193, No. 6, 1230–1233, 1970 [Russian]. Translated in Sov. Math., Dokl., 11, No. 6, 1100–1104, 1970. [13] V. V. Petrov, Predel’nye teoremy dlya summ nezavisimykh sluchainykh velichin (Limit Theorems for Sums of Independent Random Variables), Nauka, Moscow, 1987 [Russian]. Translated under the title Limit Theorems of Probability Theory: Sequences of Independent Random Variables, Clarendon Press, Oxford, 1995 (Oxf. Stud. Probab., Vol. 4). [14] D. Angluin and L. G. Valiant, Fast probabilistic algorithms for Hamiltonian circuits and matchings, J. Comput. Syst. Sci., 18, No. 2, 155–193, 1979. [15] B. Bollobás, T. I. Fenner, and A. M. Frieze, An algorithm for finding Hamilton paths and cycles in random graphs, Combinatorica, 7, No. 4, 327–341, 1987. [16] M. J. D. De Brey and A. Volgenant, Wellsolved cases of the 2peripatetic salesman problem, Optimization, 39, No. 3, 275–293, 1997. [17] J. B. J. M. De Kort, Lower bounds for symmetric $K$peripatetic salesman problems, Optimization, 22, No. 1, 113–122, 1991. [18] J. B. J. M. De Kort, Bounds for the symmetric $K$peripatetic salesman problem, Optimization, 23, No. 4, 357–367, 1992. [19] J. B. J. M. De Kort, A branch and bound algorithm for symmetric 2peripatetic salesman problems, Eur. J. Oper. Res., 70, No. 2, 229–243, 1993. [20] P. Erdös and A. Rényi, On random graphs I, Publ. Math., 6, 290–297, 1959. [21] A. M. Frieze, An algorithm for finding Hamilton cycles in random directedgraphs, J. Algorithms, 9, No. 2, 181–204, 1988. [22] A. M. Frieze and S. Haber, An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three, Random Struct. Algorithms, 47, No. 1, 73–98, 2015. [23] E. Kh. Gimadi, A. N. Glebov, A. A. Skretneva, O. Yu. Tsidulko, and D. Zh. Zambalaeva, Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph, Discrete Appl. Math., 196, No. 11, 54–61, 2015. [24] A. N. Glebov and A. V. Gordeeva, An algorithm with approximation ratio 5/6 for the metric maximum $m$PSP, in Discrete Optimization and Operations Research (Proc. 9th Int. Conf. DOOR, Vladivostok, Russia, Sept. 19–23, 2016), pp. 159–170, Springer, Cham, Switzerland, 2016 (Lect. Notes Comput. Sci., Vol. 9869). [25] J. Komlós and E. Szemerédi, Limit distributions for the existence of Hamilton circuits in a random graph, Discrete Math., 43, No. 1, 55–63, 1983. [26] J. Krarup, The peripatetic salesman and some related unsolved problems, in Combinatorial Programming: Methods and Applications, (Proc. NATO Adv. Study Inst., Versailles, France, Sept. 2–13, 1974), pp. 173–178, D. Reidel, Dordrecht, 1975 (NATO Adv. Study Inst. Ser., Vol. 19). [27] L. Posa, Hamiltonian circuits in random graphs, Discrete Math., 14, No. 4, 359–364, 1976. 

© Sobolev Institute of Mathematics, 2015  