On 2-Capacitated Peripatetic Salesman Problem with Different Weight Functions

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

Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 14 (2014) no. 3, pp. 3-18

Résumé

We considered a particular case of a problem of finding $m$ Hamiltonian cycles with capacity restrictions on edges usage ($m$-Capacitated Peripatetic Salesman Problem, $m$-CPSP): the $2$-CPSP on minimum and maximum with edge weights from an integer segment $\{1,q\}$ with different weight functions. The edges capacities are independent identically distributed random variables, which is $2$ with probability $p$ and is $1$ with probability $(1-p)$. A polynomial algorithms for $2$-CPSP$_{\min}^d$ and $2$-CPSP$_{\max}^d$ with guarantee approximation ratio in average for all possible inputs was presented. In the case when edge weights are $1$ and $2$, the presented algorithms have approximation ratios $(19-5p)/12$ and $(25 + 7p)/36$ for the $2$-CPSP$_{\min}^d$ and the $2$-CPSP$_{\max}^d$ correspondingly.

Détail

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