Geodesic
A polynomial $3/5$-approximate algorithm for~the~asymmetric maximization version of $3$-PSP
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 2, pp. 30-59.

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

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

[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 | Zbl

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

[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

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

[5] E. 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

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

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

[8] 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. Electron. Math. Izv., 8 (2011), 296–309 (Russian) | MR | Zbl

[9] 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

[10] 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

[11] A. N. Glebov, D. Zh. Zambalaeva, A. A. Skretneva, “A $2/3$-approximation algorithm for the maximum assymetric 2-Peripatetic Salesmen Problem”, Diskretn. Anal. Issled. Oper., 21:6 (2014), 11–20 (Russian) | Zbl

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

[13] 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

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

[15] De Kort J. B. J. M., “Upper bounds for the symmetric 2-PSP”, Optimization, 23:4 (1992), 357–367 | DOI | MR | Zbl

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

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

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

[19] Gimadi E. Kh., “Approximation efficient algorithms with performance guarantees for some hard routing problems”, Proc. 2nd Int. Conf. Optimization and Applications, OPTIMA-2011 (Petrovac, Montenegro, Sertember 25–October 2, 2011), VC RAN, M., 2011, 98–101

[20] 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. DOOR (Vladivostok, Russia, Sept. 19–23, 2016), Lect. Notes Comput. Sci., 9869, Springer, Cham, 2016, 159–170 | DOI | MR | Zbl

[21] Gutin G., Punnen A. P. (eds.), The Traveling Salesman Problem and its variations, Kluwer Acad. Publ., Dordrecht–Boston–London, 2002 | MR | Zbl

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

[23] Hopcroft J. E., Karp R. M., “An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs”, SIAM J. Comput., 2:4 (1973), 225–231 | DOI | MR | Zbl

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

[25] Krarup J., “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. and Phys. Sci., 19, Reidel, Dordrecht, 1975, 173–178 | MR

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

[27] Wolfter Calvo R., Cordone R., “A heuristic approach to the overnight security service problem”, Comput. Oper. Res., 30 (2003), 1269–1287 | DOI