On $m$-capacitated peripatetic salesman problem

E. Kh. Gimadi ; A. M. Istomin ; I. A. Rykov

Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 5, pp. 13-30

Résumé

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.

Détail

Keywords: travelling salesman problem, $m$-peripatetic salesman problem, approximation algorithm, edge-disjoint Hamiltonian cycle, guarantee approximation ratio.