An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem

We study a generalization of the classical Hamiltonian path problem, where multiple salesmen are positioned at the same depot, of which no more than k can be selected to service n destinations, with the objective to minimize the total travel distance. Distances between destinations (and the single depot) are assumed to satisfy the triangle inequality. We develop a non-trivial extension of the well-known Christofides heuristic for this problem, which achieves an approximation ratio of \(2-1/(2+k)\) $2-1/(2+k)$ with \(O(n^3)\) $O(n^3)$ running time for arbitrary \(k\ge 1\) $k\ge 1$ .