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, 2019, 13:2, 219-238

Volume 26, No 2, 2019, P. 30-59

UDC 519.8
A. N. Glebov and S. G. Toktokhoeva
A polynomial 3/5-approximate algorithm for the asymmetric maximization version of 3-PSP

Abstract:
We present a first polynomial algorithm with guaranteed approximation ratio for the asymmetric maximization version of the asymmetric 3-Peripatetic Salesman Problem (3-APSP). This problem consists in finding the three edge-disjoint Hamiltonian circuits of maximal total weight in a complete weighted digraph. We prove that the algorithm has guaranteed approximation ratio 3/5 and cubic running-time.
Illustr. 18, bibliogr. 27.

Keywords: Hamiltonian cycle, traveling salesman problem, $m$-peripatetic salesman problem, approximation algorithm, guaranteed approximation ratio.

DOI: 10.33048/daio.2019.26.622

Alexey N. Glebov 1,2
Surena G. Toktokhoeva 2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: angle@math.nsc.ru, s.toktokhoeva@ya.ru

Received June 6, 2018
Revised November 27, 2018
Accepted November 28, 2018

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, Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space, Tr. Inst. Mat. Mekh., 14, No. 2, 23–32, 2008 [Russian]. Translated in Proc. Steklov Inst. Math., 263, Suppl. 2, S57–S67, 2008.

[6] 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.

[7] E. Kh. Gimadi and E. V. Ivonina, Approximation algorithms for the maximum 2-Peripatetic Salesman Problem, Diskretn. Anal. Issled. Oper., Ser. 2, 19, No. 1, 17–32, 2012 [Russian]. Translated in J. Appl. Ind. Math., 6, No. 3, 295–305, 2012.

[8] A. N. Glebov, A. V. Gordeeva, and D. Zh. Zambalaeva, An algorithm with approximation ratio 7/5 for the minimum 2-Peripatetic Salesmen Problem with different weight functions, Sib. Electron. Math. Izv., 8, 296–309, 2011 [Russian].

[9] A. N. Glebov and D. Zh. Zambalaeva, A polynomial algorithm with approximation ratio 7/9 for the maximum 2-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.

[10] A. N. Glebov and D. Zh. Zambalaeva, An approximation algorithm for the minimum 2-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.

[11] A. N. Glebov, D. Zh. Zambalaeva, and A. A. Skretneva, A 2/3-approximation algorithm for the maximum assymetric 2-Peripatetic Salesmen Problem, Diskretn. Anal. Issled. Oper., 21, No. 6, 11–20, 2014 [Russian].

[12] A. I. Serdyukov, An algorithm with an estimate for the Traveling Salesman Problem of the maximum, Upravlyaemye Sistemy, Vol. 25, pp. 80–86, Inst. Mat. SO AN SSSR, Novosibirsk, 1984 [Russian].

[13] M. J. D. De Brey and A. Volgenant, Well-solved cases of the 2-Peripatetic Salesman Problem, Optimization, 39, No. 3, 275–293, 1997.

[14] J. B. J. M. De Kort, Lower bounds for symmetric K-PSP, Optimization, 22, No. 1, 113–122, 1991.

[15] J. B. J. M. De Kort, Upper bounds for the symmetric 2-PSP, Optimization, 23, No. 4, 357–367, 1992.

[16] J. B. J. M. De Kort, A branch and bound algorithm for symmetric 2-PSP, Eur. J. Oper. Res., 70, 229–243, 1993.

[17] S. Dudycz, J. Marcinkowski, K. Paluch, and B. A. Rybicki, 4/5-Approximation algorithm for the maximum Traveling Salesman Problem, in Integer Programming and Combinatorial Optimization (Proc. 19th Int. Conf., Waterloo, ON, Canada, June 26–28, 2017), pp. 173–185, Springer, 2017 (Lect. Notes Comput. Sci.,
Vol. 10328).

[18] H. N. Gabow, An efficient reduction technique for degree-restricted subgraph and bidirected network flow problems, in Proc. 15th Annu. ACM Symp. Theory Comput., Boston, USA, Apr. 25–27, 1983, pp. 448–456, ACM, New York, 1983.

[19] E. Kh. Gimadi, Approximation efficient algorithms with performance guarantees for some hard routing problems, in Proc. II Int. Conf. “Optimization and Applications”, Petrovac, Montenegro, Sept. 25 – Oct. 2, 2011, pp. 98–101, VTs RAN, Moscow, 2011.

[20] 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, 2016 (Lect. Notes Comput. Sci., Vol. 9869).

[21] G. Gutin and A. P. Punnen, eds., The Traveling Salesman Problem and Its Variations, Kluwer Acad. Publ., Dordrecht, 2002.

[22] R. Hassin and S. Rubinstein, Better approximations for max TSP, Inf. Process. Lett., 75, No. 4, 181–186, 2000.

[23] J. E. Hopcroft and R. M. Karp, An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, No. 4, 225–231, 1973.

[24] H. Kaplan, M. Lewenstein, N. Shafrir, and M. Sviridenko, Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs, J. ACM, 52, No. 4, 602–626, 2005.

[25] 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, Reidel, Dor?drecht, 1975 (NATO Adv. Study Inst. Ser., Vol. 19).

[26] K. Paluch, M. Mucha, and A. Madry, A 7/9-approximation algorithm for the maximum Traveling Salesman Problem, in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (Proc. 12th Int. Workshop and 13th Int. Workshop, Berkeley, CA, USA, Aug. 21–23, 2009), pp. 298–311, Springer, Heidelberg, 2009 (Lect. Notes Comput. Sci., Vol. 5687).

[27] R. Wolfter Calvo and R. Cordone, A heuristic approach to the overnight security service problem, Comput. Oper. Res., 30, 1269–1287, 2003.
 © Sobolev Institute of Mathematics, 2015