Geodesic
Approximation algorithms for maximum-weight problem of two-peripatetic salesmen
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 1, pp. 17-32

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

We consider the problem of finding two edge-disjoint Hamiltonian circuits (salesman routes) on maximum total weight in a complete undirected graph. In the case of edge weights in the interval $[1,q]$ a polynomial algorithm with performance ratio $\frac{3q+2}{4q+1}$ is constructed. In the case of different weight functions valued 1 and 2 a polynomial algorithm with performance ratio $\frac{11\rho-8}{18\rho-15}$ is presented, where $\rho$ is a guaranteed ratio of an algorithm for solving similar problem on minimum. Ill. 1, bibliogr. 13.
Keywords: traveling salesman problem, 2-peripatetic salesman problem, guaranteed approximation ratio.
Mots-clés : polynomial algorithm 
@article{DA_2012_19_1_a1,
     author = {E. Kh. Gimadi and E. V. Ivonina},
     title = {Approximation algorithms for maximum-weight problem of two-peripatetic salesmen},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {17--32},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_1_a1/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - E. V. Ivonina
TI  - Approximation algorithms for maximum-weight problem of two-peripatetic salesmen
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 17
EP  - 32
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_1_a1/
LA  - ru
ID  - DA_2012_19_1_a1
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A E. V. Ivonina
%T Approximation algorithms for maximum-weight problem of two-peripatetic salesmen
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 17-32
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_1_a1/
%G ru
%F DA_2012_19_1_a1
E. Kh. Gimadi; E. V. Ivonina. Approximation algorithms for maximum-weight problem of two-peripatetic salesmen. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 1, pp. 17-32. http://geodesic.mathdoc.fr/item/DA_2012_19_1_a1/