Geodesic
Probabilistic analysis of an approximation algorithm for the $m$-peripatetic salesman problem on random instances unbounded from above
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 2, pp. 88-98

Voir la notice de l'article provenant de la source Math-Net.Ru

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, distribution function, truncated normal, exponential.
Mots-clés : random instances 
@article{TIMM_2014_20_2_a7,
     author = {E. Kh. Gimadi and A. M. Istomin and I. A. Rykov and O. Yu. Tsidulko},
     title = {Probabilistic analysis of an approximation algorithm for the $m$-peripatetic salesman problem on random instances unbounded from above},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {88--98},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2014_20_2_a7/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - A. M. Istomin
AU  - I. A. Rykov
AU  - O. Yu. Tsidulko
TI  - Probabilistic analysis of an approximation algorithm for the $m$-peripatetic salesman problem on random instances unbounded from above
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2014
SP  - 88
EP  - 98
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2014_20_2_a7/
LA  - ru
ID  - TIMM_2014_20_2_a7
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A A. M. Istomin
%A I. A. Rykov
%A O. Yu. Tsidulko
%T Probabilistic analysis of an approximation algorithm for the $m$-peripatetic salesman problem on random instances unbounded from above
%J Trudy Instituta matematiki i mehaniki
%D 2014
%P 88-98
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2014_20_2_a7/
%G ru
%F TIMM_2014_20_2_a7
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 Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 2, pp. 88-98. http://geodesic.mathdoc.fr/item/TIMM_2014_20_2_a7/