Approximation algorithms for maximum-weight problem of two-peripatetic salesmen

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.