A polynomial $3/5$-approximate algorithm for the asymmetric maximization version of $3$-PSP

We present a first polynomial algorithm with guaranteed approximation ratio for the asymmetric maximization version of the asymmetric $3$-Peripatetic Salesman Problem ($3$-APSP). This problem consists in finding the three edge-disjoint Hamiltonian circuits of maximal total weight in a complete weighted digraph. We prove that the algorithm has guaranteed approximation ratio $3/5$ and cubic running-time. Illustr. 18, bibliogr. 27.