Volume 21, No 6, 2014, P. 1120
UDC 519.172.2
A. N. Glebov, D. Zh. Zambalaeva and A. A. Skretneva
2/3approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem
Abstract:
We present a polynomial approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem which consists in finding two edgedisjoint 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, polynomial algorithm, guaranteed ratio, directed graph.
Glebov Alexey Nikolaevich ^{1}
Zamabalaeva Dolgor Zhamyanovna ^{1}
Skretneva Anastasia Andreevna ^{1}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
email: angle@math.nsc.ru, dolgorzam@gmail.com, skretneva@gmail.com
