Volume 16, No 4, 2009, P. 320
UDC 519.178
A. A. Ageev, A. V. Pyatkin
A 2approximation algorithm for the metric 2peripatetic salesman problem
Abstract:
In the $m$peripatetic traveling salesman problem, given an $n$vertex complete undirected edgeweighted 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 2PSP is NPhard even in the metric case and does not admit any constantfactor approximation in the general case. Baburin, Gimadi, and Korkishko (2004) designed a $(9/4+\varepsilon)$approximation algorithm for the metric case of 2PSP, based on solving the traveling salesman problem. In the paper we present an improved 2approximation algorithm with running time $O(n^2\log n)$ for the metric 2PSP. 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
email: ageev@math.nsc.ru, artem@math.nsc.ru
