Probabilistic analysis of an approximation algorithm for the $m$-peripatetic salesman problem on random instances unbounded from above

E. Kh. Gimadi   ; A. M. Istomin   ; I. A. Rykov   ; O. Yu. Tsidulko

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 2, pp. 88-98

Résumé

We present the probabilistic analysis of an approximation algorithm for the minimum-weight $m$-peripatetic salesman problem with different weight functions of their routes (Hamiltonian cycles). The time complexity of the algorithm is $O(mn^2)$. We assume that the entries of the distance matrix are independent equally distributed random variables with values in an upper-unbounded domain $[a_n,\infty)$, where $a_n>0$. The analysis is carried out for the example of truncated normal and exponential distributions. Estimates for the relative error and failure probability, as well as conditions for the asymptotic exactness of the algorithm, are found.

Détail

Keywords: $m$-peripatetic salesman problem, approximation algorithm, time complexity, asymptotic optimality, distribution function, truncated normal, exponential.
Mots-clés : random instances

Bibliographie

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

[2] Frieze A. M., “On random symmetric traveling salesman problems”, Math. Oper. Res., 29:4 (2004), 878–890 | DOI | MR | Zbl

[3] Gimadi Edward Kh., “On some probability inequalities for some discrete optimization problems”, Oper. Res. Proc. 2005, Selected papers Int. Conf. OR-2005, Springer, Bremen–Berlin, 2006, 283–289 | DOI | Zbl

[4] Gimadi Edward Kh., “Approximation efficient algorithms with performance guarantees for some hard routing problems”, Proc. II Int. Conf. “Optimization and Applications” (OPTIMA 2011), Petrovac, 2011, 98–101

[5] Krarup J., “The peripatetic salesman and some related unsolved problems”, Combinatorial programming: methods and applications, NATO Advanced Study Inst. Ser., Ser. C: Math. and Phys. Sci., 19, ed. C. R. Reeves, Reidel, Dordrecht, 1975, 173–178 | MR

[6] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys (eds.), The traveling salesman problem: A guided tour of combinatorial optimization, Wiley, Chichester, 1985, 463 pp. | MR | Zbl

[7] G. Gutin, A. Punnen (eds.), The traveling salesman problem and its variations, Comb. Optim., 12, Kluwer Acad. Publ., Dortrecht, 2002, 830 pp. | MR

[8] Baburin A. E., Gimadi E. Kh., “Ob asimptoticheskoi tochnosti effektivnogo algoritma resheniya zadachi $m$-PSP na maksimum v mnogomernom evklidovom prostranstve”, Tr. In-ta matematiki i mekhaniki UrO RAN, 16, no. 3, 2010, 12–24

[9] Gimadi E. Kh., Glazkov Yu. V., Tsidulko O. Yu., “Veroyatnostnyi analiz algoritma resheniya trekhindeksnoi $m$-sloinoi planarnoi zadachi o naznacheniyakh na odnotsiklicheskikh podstanovkakh”, Diskretnyi analiz i issledovanie operatsii, 21:1 (2014), 15–29

[10] Gimadi E. Kh., Le Gallu A., Shakhshneider A. V., “Veroyatnostnyi analiz odnogo algoritma priblizhennogo resheniya zadachi kommivoyazhera na neogranichennykh sverkhu vkhodnykh dannykh”, Diskretnyi analiz i issledovanie operatsii, 15:1 (2008), 23–43 | MR | Zbl

[11] Gimadi E. Kh., Perepelitsa V. A., “Asimptoticheskii podkhod k resheniyu zadachi kommivoyazhera”, Upravlyaemye sistemy, 12, In-t matematiki SO AN SSSR, Novosibirsk, 1974, 35–45 | Zbl

[12] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[13] Perepelitsa V. A., Gimadi E. Kh., “Zadacha nakhozhdeniya minimalnogo gamiltonova tsikla v vzveshennom grafe”, Diskretnyi analiz, 15, In-t matematiki SO AN SSSR, Novosibirsk, 1969, 57–65 | MR

[14] Petrov V. V., Predelnye teoremy dlya summ nezavisimykh sluchainykh velichin, Nauka, M., 1987, 321 pp. | MR