EN|RU
About Journal
Editorial Board

Publishing Ethics
Author Guide Submission
 Prepare Your Manuscript
Peer review
Archive

English version:
Journal of Applied and Industrial Mathematics, 2017, 11:3, 354-361

Volume 24, No 3, 2017, P. 5-19

UDC 519.8
E. Kh. Gimadi and O. Yu. Tsidulko
An asymptotically optimal algorithm for the $m$-Peripatetic Salesman Problem on random inputs
with discrete distribution

Abstract:
We consider the $m$-Peripatetic Salesman Problem ($m$-PSP) on random inputs with discrete distribution function. In this paper we present a polynomial approximation algorithm which, under certain conditions, with high probability (w.h.p.) gives optimal solution for both the $m$-PSP on random inputs with identical weight functions and the $m$-PSP with different weight functions.
Illustr. 1, bibliogr. 27.

Keywords: $m$-Peripatetic Salesman Problem, asymptotically optimal algorithm, random inputs, discrete distribution.

DOI: 10.17377/daio.2017.24.551

Edward Kh. Gimadi 1,2
Oxana Yu. Tsidulko 1,2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: gimadi@math.nsc.ru, tsidulko.ox@gmail.com

Received 3 August 2016
Revised 13 October 2016

References

[1] A. A. Ageev, A. E. Baburin, and E. Kh. Gimadi, A 3/4-approximation 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 2-approximation algorithm for the metric 2-peripatetic 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 edge-disjoint 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 2-peripatetic 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 3-dimensional assignment problem on one-cycle 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 2-peripatetic 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, Well-solved cases of the 2-peripatetic 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 2-peripatetic 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