Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max

A. N. Glebov ; S. S. Lylova ; S. G. Toktokhoeva

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 2, pp. 923-941

Résumé

We present new polynomial approximation algorithms for the $2$-Perpatetic Salesman Problem and the $2$-Cycle Cover Problem. The $m$-Perpatetic Salesman Problem ($m$-PSP) is a generalization of the classical Traveling Salesman Problem. In the $m$-PSP, we need to find $m$ edge disjoint Hamiltonian cycles of the extremal total weight in a complete weighted graph $G=(V,E)$. In the $m$-Cycle Cover Problem ($m$-CC), we need to find $m$ edge disjoint cycle covers of the extremal weight in $G$. Many exact and approximation algorithms were proposed for the case of $m$-PSP where we are given only one weight function $w:E \rightarrow R^+$ and the weight of $m$ Hamiltonian cycles $H_1,H_2,\ldots,H_m$ is defined as $w(H_1)+ \ldots +w(H_m)$. However, not so many results are known for the case when we are given $m$ distinct weight functions $w_1,w_2,\ldots,w_m$ and the weight of $H_1,H_2,\ldots,H_m$ is defined as $w_1(H_1)+w_2(H_2)+\ldots +w_m(H_m)$ (the $m$-PSP-$m$W problem). Here we present a series of polynomial algorithms with approximation ratios $1/2$ and higher for the $2$-PSP-max-2W. As a supporting result, we produce a polynomial algorithm with the asymptotic ratio $\frac 23$ for the $2$-CC-max-$2W$ problem.

Détail

Keywords: Traveling Salesman Problem, $2$-Perpatetic Salesman Problem, Cycle Cover Problem, approximation algorithm, guaranteed approximation ratio, weight function.