Geodesic
A 2-approximation algorithm for the metric 2-peripatetic salesman problem
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 4, pp. 3-20

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

In the $m$-peripatetic traveling salesman problem, given an $n$-vertex complete undirected edge-weighted graph, it is required to find $m$ edge disjoint Hamiltonian cycles of minimum total weight. The problem was introduced by Krarup (1974) and has network design and scheduling applications. It is known that 2-PSP is NP-hard even in the metric case and does not admit any constant-factor approximation in the general case. Baburin, Gimadi, and Korkishko (2004) designed a $(9/4+\varepsilon)$-approximation algorithm for the metric case of 2-PSP, based on solving the traveling salesman problem. In the paper we present an improved 2-approximation algorithm with running time $O(n^2\log n)$ for the metric 2-PSP. Our algorithm exploits the fact that the problem of finding two edge disjoint spanning trees of minimum total weight is polynomially solvable. Il. 5, bibl. 12.
Keywords: approximation algorithm, Hamiltonian cycle, spanning tree, traveling salesman problem. 
@article{DA_2009_16_4_a0,
     author = {A. A. Ageev and A. V. Pyatkin},
     title = {A 2-approximation algorithm for the metric 2-peripatetic salesman problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--20},
     publisher = {mathdoc},
     volume = {16},
     number = {4},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_4_a0/}
}
TY  - JOUR
AU  - A. A. Ageev
AU  - A. V. Pyatkin
TI  - A 2-approximation algorithm for the metric 2-peripatetic salesman problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 3
EP  - 20
VL  - 16
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_4_a0/
LA  - ru
ID  - DA_2009_16_4_a0
ER  - 
%0 Journal Article
%A A. A. Ageev
%A A. V. Pyatkin
%T A 2-approximation algorithm for the metric 2-peripatetic salesman problem
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 3-20
%V 16
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2009_16_4_a0/
%G ru
%F DA_2009_16_4_a0
A. A. Ageev; A. V. Pyatkin. A 2-approximation algorithm for the metric 2-peripatetic salesman problem. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 4, pp. 3-20. http://geodesic.mathdoc.fr/item/DA_2009_16_4_a0/