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/

[1] Ageev A. A., Baburin A. E., Gimadi E. Kh., “Polinomialnyi algoritm s otsenkoi tochnosti 3/4 dlya otyskaniya dvukh neperesekayuschikhsya gamiltonovykh tsiklov maksimalnogo vesa”, Diskret. analiz i issled. operatsii. Ser. 1, 13:2 (2006), 11–20 | MR

[2] Baburin A. E., Gimadi E. Kh., Korkishko N. M., “Priblizhennye algoritmy dlya nakhozhdeniya dvukh reberno neperesekayuschikhsya gamiltonovykh tsiklov minimalnogo vesa”, Diskret. analiz i issled. operatsii. Ser. 2, 11:1 (2004), 11–25 | MR | Zbl

[3] Serdyukov A. I., “Nekotorye ekstremalnye obkhody v grafakh”, Upravlyaemye sistemy, 17, 1978, 76–79 | MR | Zbl

[4] Christofides N., Worst-case analysis of a new heuristic for the traveling salesman problem, Technical Report CS–93–13, Carnegie–Mellon Univ., Pittsburgh, 1976, 10 pp.

[5] De Brey M. J. D., Volgenant A., “Well-solved cases of the 2-peripatetic salesman problem”, Optimization, 39:3 (1997), 275–293 | DOI | MR | Zbl

[6] Duchenne E., Laporte G., Semet F., “Branch-and-cut algorithms for the undirected $m$-peripatetic salesman problem”, Europ. J. Oper. Res., 162:3 (2005), 700–712 | DOI | MR | Zbl

[7] De Kort J. B. J. M., “Lower bounds for symmetric $K$-peripatetic salesman problems”, Optimization, 22:1 (1991), 113–122 | DOI | MR | Zbl

[8] De Kort J. B. J. M., “Upper bounds for the symmetric 2-peripatetic salesman problem”, Optimization, 23:4 (1992), 357–367 | DOI | MR | Zbl

[9] De Kort J. B. J. M., “A branch and bound algorithm for symmetric 2-peripatetic salesman problems”, Europ. J. Oper. Res., 70 (1993), 229–243 | DOI | Zbl

[10] Krarup J., “The peripatetic salesman and some related unsolved problems”, Combinatorial programming: methods and applications, Proc. NATO Advanced Study Inst. (Versailles, 1974), Reidel Press, Dordrecht, 1975, 173–178 | MR

[11] Roskind J., Tarjan R. E., “A note on finding minimum-cost edge-disjoint spanning trees”, Math. Oper. Res., 10:4 (1985), 701–708 | DOI | MR | Zbl

[12] Wolfter C. R., Cordone R., “A heuristic approach to the overnight security service problem”, Computers Oper. Res., 30 (2003), 1269–1287 | DOI