Probabilistic analysis of an approximation algorithm for the \(m\)-peripatetic salesman problem on random instances unbounded from above (Q492278)

Given a graph \(G=(V,E)\) and \(m\) different weight-functions \(w_{1}:E \rightarrow \mathbb{R}_{+}, \dots, w_{m}:E \rightarrow \mathbb{R}_{+}\), the \(m\)-peripatetic salesman problem (\(m\)-PSP) with different weight-functions is to determine \(m\) edge-disjoint Hamiltonian cycles \(H_{1}, \dots, H_{m} \subseteq E\) with minimum (maximum) total weight \(W(H_{1}, \dots, H_{m})=\sum_{k=1}^{m} \sum_{e \in H_{k}} w_{k}(e)\). The authors consider the special case where the elements of the distance matrix are independent identically distributed random variables with values in an upper unbounded domain \([a_{n}, \infty)\) with \(a_{n}>0\), and the distribution is normal or exponential. The algorithm presented is a modification of the algorithm ``Go to the nearest not yet visited city'' and it has the time complexity \(O(mn^2)\). It is shown to be asymptotically exact if \(\beta_{n}/a_{n}=o(n/d(n))\), where \(d(n)=\)ln \(n\) for \(2 \leq m <\) ln \(n\) and \(d(n)=n^{\theta}\) for ln \(n \leq m \leq n^{1-\theta}\) and \(0 < \theta < 1\). Here, \(\beta(n)\) stands for the parameter \(\alpha(n)\) or \(\sigma(n)\) of the exponential and normal distributions, respectively.