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/