Reducing Prize-Collecting Stroll and Related Routing Problems to Prize-Collecting TSP

Abstract

The prize-collecting stroll is the path version of the prize-collecting TSP. Given a complete metric graph, two distinct prescribed terminal vertices $s,t$, and nonnegative penalties on vertices, the prize-collecting stroll asks for an $s$-$t$ tour minimizing its length plus the total penalty of vertices that are not visited by it. We study a common generalization of the prize-collecting stroll and several related prize-collecting routing problems, which we call the prize-collecting-$\Phi$-TSP. In this model, $\Phi$ specifies a set of prescribed vertices together with their parity and connectivity requirements. We show that, if a $\rho$-approximation algorithm for the prize-collecting TSP is available, then, for every fixed $\epsilon >0$, there is a polynomial-time $(\rho +\epsilon )$-approximation algorithm for the prize-collecting-$\Phi$-TSP when the number of prescribed vertices is bounded by a fixed constant. Consequently, the prize-collecting stroll can be approximated as well as the prize-collecting TSP up to an arbitrarily small additive loss in the approximation ratio. This yields a better-than-$1.6$-approximation algorithm for the prize-collecting stroll, improving the previous best-known approximation guarantee of $1.6662$.

16 pages, 5 figures