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

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