EN|RU Volume 20, No 5, 2013, P. 13-30 UDC 519.8 Gimadi E. Kh., Istomin A. M., Rykov I. A. On m-capacitated peripatetic salesman problem Abstract: We consider a particular case of the problem of finding $m$ Hamiltonian cycles with capacity restrictions on edges usage ($m$-Capacitated Peripatetic Salesman Problem, $m$-$\mathrm{CPSP}$): the $2$-CPSP on minimum and maximum with edge weights from an integer segment $\{1,q\}$. The edges capacities are independent identically distributed random variables which assume $2$ with probability $p$ and $1$ with probability $1-p$. Polynomial algorithms for $2$-$\mathrm{CPSP_{min}}$ and $2$-$\mathrm{CPSP_{max}}$ with guarantee approximation ratio in average for all possible inputs are presented. In the case when edge weights are $1$ and $2$, the presented algorithms have approximation ratio $(19-5p)/12$ and $(25+7p)/36$ for the $2$-$\mathrm{CPSP_{min}}$ and the $2$-$\mathrm{CPSP_{max}}$ correspondingly. Ill. 17, bibliogr. 20. Keywords: travelling salesman problem, m-peripatetic salesman problem, approximation algorithm, edge-disjoint Hamiltonian cycle, guarantee approximation ratio. Gimadi Edward Khairutdinovich 1,2 Istomin Alexey Mikhailovich 1 Rykov Ivan Alexandrovich 1,2 1. S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia 2. Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia e-mail: gimadi@math.nsc.ru, alexeyistomin@gmail.com, rykovweb@gmail.com © Sobolev Institute of Mathematics, 2015