Geodesic
7/5-approximation algorithm for 2-PSP on minimum with different weight functions
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 8 (2011), pp. 296-309.

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

We present a cubic time algorithm with approximation ratio 7/5 (plus some additive constant) for the 2-Peripatetic Salesman Problem on minimum with different weight functions valued 1 and 2 (abbreviated to as 2-PSP(1,2)-min-2w). Our result improves the other known algorithm for this problem which has approximation ratio 11/7.
Keywords: Traveling Salesman Problem, 2-Peripatetic Salesman Problem, guaranteed approximation ratio.
Mots-clés : polynomial algorithm 
@article{SEMR_2011_8_a24,
     author = {A. N. Glebov and A. V. Gordeeva and D. Zh. Zambalayeva},
     title = {7/5-approximation algorithm for {2-PSP} on minimum with different weight functions},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {296--309},
     publisher = {mathdoc},
     volume = {8},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2011_8_a24/}
}
TY  - JOUR
AU  - A. N. Glebov
AU  - A. V. Gordeeva
AU  - D. Zh. Zambalayeva
TI  - 7/5-approximation algorithm for 2-PSP on minimum with different weight functions
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2011
SP  - 296
EP  - 309
VL  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2011_8_a24/
LA  - ru
ID  - SEMR_2011_8_a24
ER  - 
%0 Journal Article
%A A. N. Glebov
%A A. V. Gordeeva
%A D. Zh. Zambalayeva
%T 7/5-approximation algorithm for 2-PSP on minimum with different weight functions
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2011
%P 296-309
%V 8
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2011_8_a24/
%G ru
%F SEMR_2011_8_a24
A. N. Glebov; A. V. Gordeeva; D. Zh. Zambalayeva. 7/5-approximation algorithm for 2-PSP on minimum with different weight functions. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 8 (2011), pp. 296-309. http://geodesic.mathdoc.fr/item/SEMR_2011_8_a24/

[1] A.A. Ageev, A.E. Baburin, E.Kh. Gimadi, “Polinomialnyi algoritm s otsenkoi tochnosti $3/4$ dlya otyskaniya dvukh neperesekayuschikhsya gamiltonovykh tsiklov maksimalnogo vesa”, Diskret. analiz i issled. operatsii, ser. 1, 13:2 (2006), 11–20 | MR | Zbl

[2] A.E. Baburin, E.Kh. Gimadi, N.M. Korkishko, “Priblizhennye algoritmy dlya nakhozhdeniya dvukh reberno neperesekayuschikhsya gamiltonovykh tsikla minimalnogo vesa”, Diskret. analiz i issled. operatsii, ser. 2, 11:1 (2004), 11–25 | MR | Zbl

[3] E.Kh. Gimadi, Yu.V. Glazkov, A.N. Glebov, “Priblizhennye algoritmy resheniya zadachi o dvukh kommivoyazherakh v polnom grafe s vesami reber 1 i 2”, Diskret. analiz i issled. operatsii, ser. 2, 14:2 (2007), 41–61 | MR | Zbl

[4] A.I. Serdyukov, “O nekotorykh ekstremalnykh obkhodakh v grafakh”, Upravlyaemye sistemy. Sb. nauch. tr., 17, 1978, 76–79 | MR | Zbl

[5] P. Berman, M. Karpinski, “$8/7$-approximation algorithm for (1,2)-TSP”, Proc. of the 17th annual ACM-SIAM symposium on discrete algorithms, SODA 2006 (Miami, January 22–26, 2006), ACM Press, New York, 2006, 641–648 | MR | Zbl

[6] N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem, Technical report CS-93-19, Carnegie Mellon University, 1976

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

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

[9] J.B. J.M. De Kort, “A branch and bound algorithm for symmetric $2$-peripatetic salesman problems”, European J. Oper. Res., 70:2 (1993), 229–243 | DOI | MR | Zbl

[10] C.H. Papadimitriou, M. Yannakakis, “The travelling salesman problem with distances One and Two”, Math. Oper. Res., 18:1 (1993), 1–11 | DOI | MR | Zbl

[11] A.E. Baburin, F. Della Croce, E.K. Gimadi, Y.V. Glazkov, V.Th. Paschos, “Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2”, Discrete Applied Mathematics, 157:9 (2009), 1988–1992 | DOI | MR | Zbl