Volume 19, No 1, 2012, P. 1732
UDC 519.8
E. Kh. Gimadi, Å. V. Ivonina
Approximation algorithms for maximumweight problem of twoperipatetic salesmen
Abstract:
We consider the problem of finding two edgedisjoint Hamiltonian circuits (salesman routes) on maximum total weight in a complete undirected graph. In the case of edge weights in the interval $[1,q]$ a polynomial algorithm with performance ratio $\frac{3q+2}{4q+1}$ is constructed. In the case of different weight functions valued 1 and 2 a polynomial algorithm with performance ratio $\frac{11\rho8}{18\rho15}$ is presented, where $\rho$ is a guaranteed ratio of an algorithm for solving similar problem on minimum.
Ill. 1, bibliogr. 13.
Keywords: traveling salesman problem, 2peripatetic salesman problem, polynomial algorithm, guaranteed approximation ratio.
Gimadi Eduard Khairutdinovich ^{1,2}
Ivonina Evgeniya Viktorovna ^{1}
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: gimadi@math.nsc.ru, evivonina@gmail.com
