An asymptotically optimal algorithm for the $m$-peripatetic salesman problem on random inputs with discrete distribution

E. Kh. Gimadi ; O. Yu. Tsidulko

Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 3, pp. 5-19.

Résumé

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.

Détail

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

Bibliographie

[1] A. A. Ageev, A. E. Baburin, E. Kh. Gimadi, “A 3/4-approximation algorithm for finding two disjoint Hamiltonian cycles of maximum weight”, J. Appl. Ind. Math., 1:2 (2007), 142–147 | DOI | MR

[2] A. A. Ageev, A. V. Pyatkin, “A 2-approximation algorithm for the metric 2-peripatetic salesman problem”, Diskretn. Anal. Issled. Oper., 16:4 (2009), 3–20 (Russian)

[3] A. E. Baburin, E. Kh. Gimadi, “On the asymptotic optimality of an algorithm for solving the maximum $m$-PSP in a multidimensional Euclidean space”, Proc. Steklov Inst. Math., 272, Suppl. 1 (2011), S1–S13 | DOI | MR | Zbl

[4] A. E. Baburin, E. Kh. Gimadi, N. M. Korkishko, “Approximation algorithms for finding two edge-disjoint Hamiltonian cycles of minimal total weight”, Diskretn. Anal. Issled. Oper., Ser. 2, 11:1 (2004), 11–25 (Russian)

[5] E. Kh. Gimadi, Yu. V. Glazkov, A. N. Glebov, “Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2”, J. Appl. Ind. Math., 3:1 (2009), 46–60 | DOI | MR | Zbl

[6] E. Kh. Gimadi, Yu. V. Glazkov, O. Yu. Tsidulko, “The probabilistic analysis of an algorithm for solving the $m$-planar 3-dimensional assignment problem on one-cycle permutations”, J. Appl. Ind. Math., 8:2 (2014), 208–217 | DOI | MR | Zbl

[7] E. Kh. Gimadi, A. M. Istomin, I. A. Rykov, O. Yu. Tsidulko, “Probabilistic analysis of an approximation algorithm for the $m$-peripatetic salesman problem on random instances unbounded from above”, Proc. Steklov Inst. Math., 289, Suppl. 1 (2015), S77–S87 | MR | Zbl

[8] E. Kh. Gimadi, E. V. Ivonina, “Approximation algorithms for the maximum 2-peripatetic salesman problem”, J. Appl. Ind. Math., 6:3 (2012), 295–305 | DOI | MR | Zbl

[9] E. Kh. Gimadi, V. A. Perepelitsa, “A statistically effective algorithm for selection of a Hamiltonian contour or cycle”, Discrete Analysis, 22, Inst. Mat. SO AN SSSR, Novosibirsk, 1973, 15–28 (Russian) | Zbl

[10] A. N. Glebov, D. Zh. Zambalaeva, “A polynomial algorithm with approximation ratio 7/9 for the maximum two peripatetic salesmen problem”, J. Appl. Ind. Math., 6:1 (2012), 69–89 | DOI | MR | Zbl

[11] A. N. Glebov, D. Zh. Zambalaeva, “An approximation algorithm for the minimum two peripatetic salesmen problem with different weight functions”, J. Appl. Ind. Math., 6:2 (2012), 167–183 | DOI | MR

[12] A. D. Korshunov, “On the power of some classes of graphs”, Sov. Math., Dokl., 11:6 (1970), 1100–1104 | MR | Zbl

[13] V. V. Petrov, Limit Theorems of Probability Theory: Sequences of Independent Random Variables, Oxf. Stud. Probab., 4, Clarendon Press, Oxford, 1995 | MR | Zbl

[14] Angluin D., Valiant L. G., “Fast probabilistic algorithms for Hamiltonian circuits and matchings”, J. Comput. Syst. Sci., 18:2 (1979), 155–193 | DOI | MR | Zbl

[15] Bollobás B., Fenner T. I., Frieze A. M., “An algorithm for finding Hamilton paths and cycles in random graphs”, Combinatorica, 7:4 (1987), 327–341 | DOI | MR | Zbl

[16] De Brey M. J. D., Volgenant A., “Well-solved cases of the 2-peripatetic salesman problem”, Optimization, 39:3 (1997), 275–293 | DOI | MR | Zbl

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

[18] De Kort J. B. J. M., “Bounds for the symmetric $K$-peripatetic salesman problem”, Optimization, 23:4 (1992), 357–367 | DOI | MR | Zbl

[19] De Kort J. B. J. M., “A branch and bound algorithm for symmetric 2-peripatetic salesman problems”, Eur. J. Oper. Res., 70:2 (1993), 229–243 | DOI | MR | Zbl

[20] Erdös P., Rényi A., “On random graphs I”, Publ. Math., 6 (1959), 290–297 | MR | Zbl

[21] Frieze A. M., “An algorithm for finding Hamilton cycles in random directed graphs”, J. Algorithms, 9:2 (1988), 181–204 | DOI | MR | Zbl

[22] Frieze A. M., Haber S., “An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three”, Random Struct. Algorithms, 47:1 (2015), 73–98 | DOI | MR | Zbl

[23] Gimadi E. Kh., Glebov A. N., Skretneva A. A., Tsidulko O. Yu., Zambalaeva D. Zh., “Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph”, Discrete Appl. Math., 196:11 (2015), 54–61 | DOI | MR | Zbl

[24] Glebov A. N., Gordeeva A. V., “An algorithm with approximation ratio 5/6 for the metric maximum $m$-PSP”, Discrete Optimization and Operations Research, Proc. 9th Int. Conf. (Vladivostok, Russia, Sept. 19–23, 2016), Lect. Notes Comput. Sci., 9869, Springer, Cham, Switzerland, 2016, 159–170 | DOI | MR

[25] Komlós J., Szemerédi E., “Limit distributions for the existence of Hamilton circuits in a random graph”, Discrete Math., 43:1 (1983), 55–63 | DOI | MR | Zbl

[26] Krarup J., “The peripatetic salesman and some related unsolved problems”, Combinatorial Programming: Methods and Applications. Proc. NATO Adv. Study Inst. (Versailles, France, Sept. 2–13, 1974), NATO Adv. Study Inst. Ser., 19, D. Reidel, Dordrecht, 1975, 173–178 | MR

[27] Posa L., “Hamiltonian circuits in random graphs”, Discrete Math., 14:4 (1976), 359–364 | DOI | MR | Zbl