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.
- asymptotically optimal algorithm
- discrete distribution
- m-Peripatetic Salesman Problem
- random inputs