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, 2020, 14:3, 456-469

Volume 27, No 3, 2020, P. 28-52

UDC 519.8
A. N. Glebov and S. G. Toktokhoeva
A polynomial algorithm with asymptotic ratio 2/3 for the asymmetric maximization version of the $m$-PSP

Abstract:
In 2005, Kaplan et al. presented a polynomial-time algorithm with guaranteed approximation ratio 2/3 for the maximization version of the asymmetric TSP. In 2014, Glebov, Skretneva, and Zambalaeva constructed a similar algorithm with approximation ratio 2/3 and cubic runtime for the maximization version of the asymmetric 2-PSP (2-APSP-max), where it is required to find two edge-disjoint Hamiltonian cycles of maximum total weight in a complete directed weighted graph. The goal of this paper is to construct a similar algorithm for the more general $m$-APSP-max in the asymmetric case and justify an approximation ratio for this algorithm that tends to 2/3 as $n$ grows and the runtime complexity estimate $O(mn^3)$.
Illustr. 2, bibliogr. 29.

Keywords: Hamiltonian cycle, Traveling Salesman Problem, $m$-Peripatetic Salesman Problem, approximation algorithm, guaranteed approximation ratio.

DOI: 10.33048/daio.2020.27.677

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 December 2, 2019
Revised May 9, 2020
Accepted May 25, 2020

References

[1] 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) (Reidel, Dordrecht, 1975), pp. 173–178 (NATO Adv. Study Inst. Ser., Vol. 19).

[2] A. A. Ageev, A. E. Baburin, and Eh. Kh. Gimadi, A 3/4 approximation algorithm for finding two disjoint Hamiltonian cycles of maximum weight, Diskretn. Anal. Issled. Oper., Ser. 1, 13 (2), 11–20 (2006) [Russian] [J. Appl. Ind. Math. 1 (2), 142–147 (2007)].

[3] 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 (4), 17–48 (2011) [Russian] [J. Appl. Ind. Math. 6 (1), 69–89 (2012)].

[4] A. E. Baburin, Eh. 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 (1), 11–25 (2004) [Russian].

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

[6] 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) (Springer, Cham, 2016), pp. 159–170 (Lect. Notes Comput. Sci., Vol. 9869).

[7] Eh. 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 (2), 23–32 (2008) [Russian] [Proc. Steklov Inst. Math. 263, Suppl. 2, S57–S67 (2008)].

[8] A. E. Baburin and Eh. 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 (3), 12–24 (2010) [Russian] [Proc. Steklov Inst. Math. 272, Suppl. 1, S1–S13 (2011)].

[9] Eh. 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 (2), 41–61 (2007) [Russian] [J. Appl. Ind. Math. 3 (1), 46–60 (2009)].

[10] 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. Elektron. Mat. Izv. 8, 296–309 (2011) [Russian].

[11] 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 (5), 11–37 (2011) [Russian] [J. Appl. Ind. Math. 6 (2), 167–183 (2012)].

[12] Eh. Kh. Gimadi and E. V. Ivonina, Approximation algorithms for the maximum 2-peripatetic salesman problem, Diskretn. Anal. Issled. Oper., Ser. 2, 19 (1), 17–32 (2012) [Russian] [J. Appl. Ind. Math. 6 (3), 295–305 (2012)].

[13] A. V. Gordeeva, Polynomial algorithms with guaranteed estimates for the metric maximum 2-peripatetic salesman problem, Grad. Thesis (NGU, Novosibirsk, 2010).

[14] R. Wolfler Calvo and R. Cordone, A heuristic approach to the overnight security service problem, Comput. Oper. Res. 30, 1269–1287 (2003).

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

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

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

[18] M. J. D. De Brey and A. Volgenant, Well-solved cases of the 2-peripatetic salesman problem, Optimization 39 (3), 275–293 (1997).

[19] The Traveling Salesman Problem and Its Variations (Kluwer Acad. Publ., Dordrecht, 2002).

[20] Eh. 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 (VTs RAN, Moscow, 2011), pp. 98–101.

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

[22] A. I. Serdyukov, An algorithm with an estimate for the traveling salesman problem of the maximum, in Control Systems, Vol. 25 (Inst. Mat. SO AN SSSR, Novosibirsk, 1984), pp. 80–86 [Russian].

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

[24] 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) (Springer, Heidelberg, 2009), pp. 298–311 (Lect. Notes Comput. Sci., Vol. 5687).

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

[26] A. N. Glebov, D. Zh. Zambalaeva, and A. A. Skretneva, A 2/3-approximation algorithm for the maximum asymmetric 2-peripatetic salesman problem, Diskretn. Anal. Issled. Oper. 21 (6), 11–20 (2014) [Russian].

[27] A. N. Glebov and S. G. Toktokhoeva, A polynomial 3/5-approximate algorithm for the asymmetric maximization version of 3-PSP, Diskretn. Anal. Issled. Oper. 26 (2), 30–59 (2019) [Russian].

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

[29] R. Cole, K. Ost, and S. Schirra, Edge-coloring bipartite multigraphs in $O$($E$ log $D$) time, Combinatorica 21 (1), 5–12 (2001).
 © Sobolev Institute of Mathematics, 2015