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