Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph

In this paper we present two new polynomial algorithms for the asymmetric version of the mm-Peripatetic Salesman Problem (mm-APSP) which consists in finding m edge-disjoint Hamiltonian circuits of extremal total weight in a complete weighted digraph. The first algorithm solves the asymmetric 2-PSP on maximum. Its approximation ratio is equal to 2/3. The second algorithm deals with the minimization version of the asymmetric m-PSP on random instances. For this algorithm conditions for asymptotically exactness are presented.