EN|RU

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

 © Sobolev Institute of Mathematics, 2015