Geodesic
Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 2, pp. 923-941.

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

We present new polynomial approximation algorithms for the $2$-Perpatetic Salesman Problem and the $2$-Cycle Cover Problem. The $m$-Perpatetic Salesman Problem ($m$-PSP) is a generalization of the classical Traveling Salesman Problem. In the $m$-PSP, we need to find $m$ edge disjoint Hamiltonian cycles of the extremal total weight in a complete weighted graph $G=(V,E)$. In the $m$-Cycle Cover Problem ($m$-CC), we need to find $m$ edge disjoint cycle covers of the extremal weight in $G$. Many exact and approximation algorithms were proposed for the case of $m$-PSP where we are given only one weight function $w:E \rightarrow R^+$ and the weight of $m$ Hamiltonian cycles $H_1,H_2,\ldots,H_m$ is defined as $w(H_1)+ \ldots +w(H_m)$. However, not so many results are known for the case when we are given $m$ distinct weight functions $w_1,w_2,\ldots,w_m$ and the weight of $H_1,H_2,\ldots,H_m$ is defined as $w_1(H_1)+w_2(H_2)+\ldots +w_m(H_m)$ (the $m$-PSP-$m$W problem). Here we present a series of polynomial algorithms with approximation ratios $1/2$ and higher for the $2$-PSP-max-2W. As a supporting result, we produce a polynomial algorithm with the asymptotic ratio $\frac 23$ for the $2$-CC-max-$2W$ problem.
Keywords: Traveling Salesman Problem, $2$-Perpatetic Salesman Problem, Cycle Cover Problem, approximation algorithm, guaranteed approximation ratio, weight function. 
@article{SEMR_2023_20_2_a35,
     author = {A. N. Glebov and S. S. Lylova and S. G. Toktokhoeva},
     title = {Approximation algorithms for {2-PSP-2W-max} and {2-CC-2W-max}},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {923--941},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a35/}
}
TY  - JOUR
AU  - A. N. Glebov
AU  - S. S. Lylova
AU  - S. G. Toktokhoeva
TI  - Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2023
SP  - 923
EP  - 941
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a35/
LA  - ru
ID  - SEMR_2023_20_2_a35
ER  - 
%0 Journal Article
%A A. N. Glebov
%A S. S. Lylova
%A S. G. Toktokhoeva
%T Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2023
%P 923-941
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a35/
%G ru
%F SEMR_2023_20_2_a35
A. N. Glebov; S. S. Lylova; S. G. Toktokhoeva. Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 2, pp. 923-941. http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a35/

[1] A.A. Ageev, A.E. Baburin, E.Kh. Gimadi, “A polynomial algorithm with an accuracy estimate of 3/4 for finding two nonintersecting Hamiltonian cycles of maximum weight”, Discretn. Anal. Issled. Oper., Ser. 1, 13:2 (2006), 11–20 | MR | Zbl

[2] A.A. Ageev, A.V. Pyatkin, “A 2-approximation algorithm for the metric 2-peripatetic salesman problem”, Discret. Anal. Issled. Oper., 16:4 (2009), 3–20 | 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), 1–13 | DOI | MR | Zbl

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

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

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

[7] R. Diestel, Graph Theory, Springer-Verlag, Berlin, 2000 | MR | Zbl

[8] 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, 19th international conference, IPCO 2017, Proceedings (Waterloo, ON, Canada, June 26-28, 2017), Lect. Notes Comput. Sci., 10328, eds. Eisenbrand Friedrich et al., Springer, Cham, 2017, 173–185 | DOI | MR | Zbl

[9] 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, April 25–27, 1983), ACM, New York, 1983, 448–456

[10] E.Kh. Gimadi, Yu.V. Glazkov, A.N. Glebov, “Approximation algorithms for solving 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2”, Diskretn. Anal. Issled. Oper., Ser. 2, 14:2 (2007), 41–61 | MR | Zbl

[11] A.N. Glebov, A.V. Gordeeva, “An algorithm with approximation ratio $5/6$ for the metric maximum $m$-PSP”, Discrete optimization and operations research, 9th international conference, DOOR 2016, Lect. Notes Comput. Sci., 9869, eds. Kochetov Yu. et al., Springer, Cham, 2016, 159–170 | DOI | MR | Zbl

[12] A.N. Glebov, A.V. Gordeeva, D.Zh. Zambalaeva, “7/5-approximation algorithm for 2-PSP on minimum with different weight functions”, Sib. Èlektron. Mat. Izv., 8 (2011), 296–309 | MR | Zbl

[13] A.N. Glebov, S.G. Toktokhoeva, “A polynomial algorithm with asymptotic ratio 2/3 for the asymmetric maximization version of the m-PSP”, J. Appl. Ind. Math., 14:3 (2020), 456–469 | DOI | MR | Zbl

[14] A.N. Glebov, D.Zh. Zambalaeva, “Polynomial algorithm with approximation ratio 7/9 for the maximum 2-peripatetic salesman problem”, Discret. Anal. Issled. Oper., 18:4 (2011), 17–48 | MR | Zbl

[15] A.N. Glebov, D.Zh. Zambalaeva, “An approximation algorithm for the minimum 2-peripatetic salesman problem with different weight functions”, Discret. Anal. Issled. Oper., 18:5 (2011), 11–37 | MR | Zbl

[16] A.N. Glebov, D.Zh. Zambalaeva, A.A. Skretneva, “A polynomial algorithm with approximation ratio 2/3 for the asymmetric maximum 2-peripatetic salesman problem”, J. Appl. Ind. Math., 9:1 (2015), 61–67 | DOI | MR | Zbl

[17] A.V. Gordeeva, Polynomial algorithms with guaranteed approximation ratios for the metric maximum 2-PSP, Graduation thesis of a specialist, Novosibirsk State University, 2010

[18] A.I. Serdyukov, “An algorithm with estimation for the travelling salesman maximum problem”, Upr. Sist., 25 (1984), 80–86 | MR | Zbl