|
Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2014, Volume 20, Number 2, Pages 88–98
(Mi timm1061)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Probabilistic analysis of an approximation algorithm for the $m$-peripatetic salesman problem on random instances unbounded from above
E. Kh. Gimadiab, A. M. Istominba, I. A. Rykovab, O. Yu. Tsidulkoba a Novosibirsk State University
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Abstract:
We present the probabilistic analysis of an approximation algorithm for the minimum-weight $m$-peripatetic salesman problem with different weight functions of their routes (Hamiltonian cycles). The time complexity of the algorithm is $O(mn^2)$. We assume that the entries of the distance matrix are independent equally distributed random variables with values in an upper-unbounded domain $[a_n,\infty)$, where $a_n>0$. The analysis is carried out for the example of truncated normal and exponential distributions. Estimates for the relative error and failure probability, as well as conditions for the asymptotic exactness of the algorithm, are found.
Keywords:
$m$-peripatetic salesman problem, approximation algorithm, time complexity, asymptotic optimality, random instances, distribution function, truncated normal, exponential.
Received: 30.01.2014
Citation:
E. Kh. Gimadi, A. M. Istomin, I. A. Rykov, O. Yu. Tsidulko, “Probabilistic analysis of an approximation algorithm for the $m$-peripatetic salesman problem on random instances unbounded from above”, Trudy Inst. Mat. i Mekh. UrO RAN, 20, no. 2, 2014, 88–98; Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 77–87
Linking options:
https://www.mathnet.ru/eng/timm1061 https://www.mathnet.ru/eng/timm/v20/i2/p88
|
Statistics & downloads: |
Abstract page: | 326 | Full-text PDF : | 75 | References: | 49 | First page: | 11 |
|