Volume 21, No 6, 2014, P. 11-20
UDC 519.172.2
A. N. Glebov, D. Zh. Zambalaeva and A. A. Skretneva
2/3-approximation 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 edge-disjoint 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
e-mail: angle@math.nsc.ru, dolgorzam@gmail.com, skretneva@gmail.com
