EN|RU Volume 16, No 4, 2009, P. 3-20 UDC 519.178 A. A. Ageev, A. V. Pyatkin A 2-approximation algorithm for the metric 2-peripatetic salesman problem Abstract: 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. Ageev Alexander Alexandrovich 1,2 Pyatkin Artem Valerievich 1,2 1. S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia 2. Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia e-mail: ageev@math.nsc.ru, artem@math.nsc.ru © Sobolev Institute of Mathematics, 2015