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/