Geodesic
$2/3$-approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 6, pp. 11-20

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

We present a polynomial approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem which consists in finding two edge-disjoint Hamiltonian circuits of maximum total weight in a complete weighted digraph. The algorithm guarantees an approximation ratio of $2/3$ in cubic running time. Ill. 5, bibliogr. 7.
Keywords: traveling salesman problem, peripatetic salesman problem, guaranteed ratio, directed graph.
Mots-clés : polynomial algorithm 
@article{DA_2014_21_6_a1,
     author = {A. N. Glebov and D. Zh. Zambalaeva and A. A. Skretneva},
     title = {$2/3$-approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {11--20},
     publisher = {mathdoc},
     volume = {21},
     number = {6},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_6_a1/}
}
TY  - JOUR
AU  - A. N. Glebov
AU  - D. Zh. Zambalaeva
AU  - A. A. Skretneva
TI  - $2/3$-approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 11
EP  - 20
VL  - 21
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_6_a1/
LA  - ru
ID  - DA_2014_21_6_a1
ER  - 
%0 Journal Article
%A A. N. Glebov
%A D. Zh. Zambalaeva
%A A. A. Skretneva
%T $2/3$-approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 11-20
%V 21
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_6_a1/
%G ru
%F DA_2014_21_6_a1
A. N. Glebov; D. Zh. Zambalaeva; A. A. Skretneva. $2/3$-approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 6, pp. 11-20. http://geodesic.mathdoc.fr/item/DA_2014_21_6_a1/