On 2-Capacitated Peripatetic Salesman Problem with Different Weight Functions

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.