2/3-APPROXIMATION ALGORITHM FOR THE MAXIMIZATION VERSION OF THE ASYMMETRIC TWO PERIPATETIC SALESMAN PROBLEM
We present a polynomial approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem which consists in finding two edge-disjoint Hamiltonian circuits of maximum total weight in a complete weighted digraph. The algorithm guarantees an approximation ratio of 2/3 in cubic running time. Ill. 5, bibliogr. 7.