POLYNOMIAL ALGORITHM WITH APPROXIMATION RATIO 7/9 FOR MAXIMUM 2-PSP
We study a 2-peripatetic salesman problem on maximum which consists in finding two edge-disjoint Hamiltonian cycles of maximum total weight in a complete undirected graph. We present a cubic time approximation algorithm for this problem with guaranteed ratio 7/9, the best known for today. 111. 5, bibliogr. 15.