Geodesic
A polynomial algorithm with~asymptotic ratio~$2/3$ for~the~asymmetric maximization version of~the~$m$-PSP
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 3, pp. 28-52.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2020_27_3_a1,
     author = {A. N. Glebov and S. G. Toktokhoeva},
     title = {A polynomial algorithm with~asymptotic ratio~$2/3$ for~the~asymmetric maximization version of~the~$m${-PSP}},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {28--52},
     publisher = {mathdoc},
     volume = {27},
     number = {3},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_3_a1/}
}
TY  - JOUR
AU  - A. N. Glebov
AU  - S. G. Toktokhoeva
TI  - A polynomial algorithm with~asymptotic ratio~$2/3$ for~the~asymmetric maximization version of~the~$m$-PSP
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 28
EP  - 52
VL  - 27
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_3_a1/
LA  - ru
ID  - DA_2020_27_3_a1
ER  - 
%0 Journal Article
%A A. N. Glebov
%A S. G. Toktokhoeva
%T A polynomial algorithm with~asymptotic ratio~$2/3$ for~the~asymmetric maximization version of~the~$m$-PSP
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 28-52
%V 27
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_3_a1/
%G ru
%F DA_2020_27_3_a1
A. N. Glebov; S. G. Toktokhoeva. A polynomial algorithm with~asymptotic ratio~$2/3$ for~the~asymmetric maximization version of~the~$m$-PSP. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 3, pp. 28-52. http://geodesic.mathdoc.fr/item/DA_2020_27_3_a1/

[1] J. Krarup, “The peripatetic salesman and some related unsolved problems”, Combinatorial programming: Methods and applications, Proc. NATO Adv. Study Inst. (Versailles, France, 1974), NATO Adv. Study Inst. Ser., Ser. C: Math. Phys. Sci., 19, Reidel, Dordrecht, 1975, 173–178 | MR

[2] A. A. Ageev, A. E. Baburin, Eh. 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 | Zbl

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

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

[5] 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) | MR | Zbl

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

[7] Eh. Kh. Gimadi, “Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space”, Proc. Steklov Inst. Math., 263, Suppl. 2 (2008), S57–S67 | DOI | MR | Zbl

[8] A. E. Baburin, Eh. 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

[9] Eh. 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 | MR | Zbl

[10] A. N. Glebov, A. V. Gordeeva, 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 (2011), 296–309 (Russian) | Zbl

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

[12] Eh. 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 | MR | Zbl

[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, R. Cordone, “A heuristic approach to the overnight security service problem”, Comput. Oper. Res., 30 (2003), 1269–1287 | DOI | Zbl

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

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

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

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

[19] The traveling salesman problem and its variations, Kluwer Acad. Publ., Dordrecht, 2002 | Zbl

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

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

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

[23] R. Hassin, S. Rubinstein, “Better approximations for max TSP”, Inf. Process. Lett., 75:4 (2000), 181–186 | DOI | MR | Zbl

[24] K. Paluch, M. Mucha, A. Madry, “A 7/9-approximation algorithm for the maximum traveling salesman problem”, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, Proc. 12th Int. Workshop, APPROX 2009 and 13th Int. Workshop RANDOM 2009 (Berkeley, CA, USA, Aug. 21–23, 2009), Lect. Notes Comput. Sci., 5687, Springer, Heidelberg, 2009, 298–311 | DOI | MR | Zbl

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

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

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

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

[29] R. Cole, K. Ost, S. Schirra, “Edge-coloring bipartite multigraphs in O(E log D) time”, Combinatorica, 21:1 (2001), 5–12 | DOI | MR | Zbl