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
