Volume 19, No 1, 2012, P. 17-32
UDC 519.8
E. Kh. Gimadi, Å. V. Ivonina
Approximation algorithms for maximum-weight problem of two-peripatetic salesmen
Abstract:
We consider the problem of finding two edge-disjoint 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\rho-8}{18\rho-15}$ 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, 2-peripatetic 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
e-mail: gimadi@math.nsc.ru, evivonina@gmail.com
