Probabilistic analysis of an approximation algorithm for the \(m\)-peripatetic salesman problem on random instances unbounded from above
type: Item
instance of: scholarly article
title: Probabilistic analysis of an approximation algorithm for the \(m\)-peripatetic salesman problem on random instances unbounded from above
zbMATH Open document ID: 1336.90073
DOI: 10.1134/S0081543815050077
author: A. M. Istomin
author: I. A. Rykov
author: O. Yu. Tsidulko
author: Eh. Kh. Gimadi
published in: Proceedings of the Steklov Institute of Mathematics
publication date: 2015-08-20T00:00:00Z
review text: 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.
reviewed by: Reinhardt Euler
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C15
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6474026
zbMATH Keywords: \(m\)-peripatetic salesman problem
zbMATH Keywords: approximation algorithm
zbMATH Keywords: time complexity
zbMATH Keywords: asymptotic optimality
zbMATH Keywords: random instances
zbMATH Keywords: density function
zbMATH Keywords: truncated normal distribution
zbMATH Keywords: exponential distribution
MaRDI profile type: Publication
cites work: A branch and bound algorithm for symmetric 2-peripatetic salesman problems
cites work: On Random Symmetric Travelling Salesman Problems
cites work: Q3416558
cites work: Q4068472
cites work: Q5187226
cites work: The traveling salesman problem and its variations
cites work: On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
cites work: Probabilistic analysis of an algorithm for the m-planar 3-index assignment problem on single-cycle permutations
cites work: Q4187615
cites work: Q4198056
cites work: Q3757055
full work available at URL: s0081543815050077
OpenAlex ID: W2473151934
description: scientific article; zbMATH DE number 6474026