Geodesic
An approximation algorithm for the minimum 2-PSP with different weight functions valued~1 and~2
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 5, pp. 11-37.

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

We present a polynomial algorithm with time complexity $O(n^5)$ and approximation ratio 4/3 (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 with approximation ratio 11/7. Ill. 3, bibliogr. 10.
Keywords: traveling salesman problem, 2-peripatetic salesman problem, guaranteed approximation ratio.
Mots-clés : polynomial algorithm 
@article{DA_2011_18_5_a1,
     author = {A. N. Glebov and D. Zh. Zambalayeva},
     title = {An approximation algorithm for the minimum {2-PSP} with different weight functions valued~1 and~2},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {11--37},
     publisher = {mathdoc},
     volume = {18},
     number = {5},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_5_a1/}
}
TY  - JOUR
AU  - A. N. Glebov
AU  - D. Zh. Zambalayeva
TI  - An approximation algorithm for the minimum 2-PSP with different weight functions valued~1 and~2
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 11
EP  - 37
VL  - 18
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_5_a1/
LA  - ru
ID  - DA_2011_18_5_a1
ER  - 
%0 Journal Article
%A A. N. Glebov
%A D. Zh. Zambalayeva
%T An approximation algorithm for the minimum 2-PSP with different weight functions valued~1 and~2
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 11-37
%V 18
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_5_a1/
%G ru
%F DA_2011_18_5_a1
A. N. Glebov; D. Zh. Zambalayeva. An approximation algorithm for the minimum 2-PSP with different weight functions valued~1 and~2. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 5, pp. 11-37. http://geodesic.mathdoc.fr/item/DA_2011_18_5_a1/

[1] Ageev A. A., Baburin A. E., Gimadi E. Kh., “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

[2] Gimadi E. Kh., Glazkov Yu. V., Glebov A. N., “Priblizhënnye algoritmy resheniya zadachi o dvukh kommivoyazhërakh v polnom grafe s vesami rëber 1 i 2”, Diskret. analiz i issled. operatsii. Ser. 2, 14:2 (2007), 41–61 | MR

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

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

[5] Berman P., Karpinski M., “$8/7$-Approximation algorithm for (1,2)-TSP”, Proc. of 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] Christofides N., Worst-case analysis of a new heuristic for the traveling salesman problem, Technical report CS-93-19, Carnegie Mellon University, 1976

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

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

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

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