An asymptotically optimal algorithm for the $m$-peripatetic salesman problem on random inputs with discrete distribution

We consider the $m$-Peripatetic Salesman Problem ($m$-PSP) on random inputs with discrete distribution function. In this paper we present a polynomial approximation algorithm which, under certain conditions, with high probability (w.h.p.) gives optimal solution for both the $m$-PSP on random inputs with identical weight functions and the $m$-PSP with different weight functions. Illustr. 1, bibliogr. 27.