The probabilistic analysis of an algorithm for solving the $m$-planar $3$-dimensional assignment problem on one-cycle permutations

We study the $m$-planar $3$-dimensional assignment problem on one-cycle permutations. In other words, it is the $m$-peripatetic salesman problem ($m$-PSP) with different weight functions for each salesman. The problem is NP-hard for $m\ge1$. We introduce a polynomial approximation algorithm suggested for $1<m<n/4$ with time complexity $O(mn^2)$. The performance ratios of the algorithm are established for input data (elements of $(m\times n\times n)$-matrix) which are assumed to be independent and identically distributed random variables on $[a_n,b_n]$, where $0<a_n<b_n$. If the distribution is uniform or dominates the uniform distribution, conditions on $a_n,b_n$ and $m$ are obtained for the asymptotic optimality of the algorithm. Ill. 1, bibliogr. 26.