Approximating Prize-Collecting TSP below 1.556

Abstract

The prize-collecting traveling salesperson problem is a variant of the metric traveling salesperson problem in which vertices may be left unvisited by paying their associated penalties. The objective is to minimize the length of the tour plus the total penalty of the unvisited vertices. Blauth, Klein, and Nägele gave the previously best-known LP-relative $1.599$-approximation. Their algorithm constructs tours by applying a splitting-off preprocessing to an LP solution, decomposing the resulting solution into trees, pruning them, and performing parity correction. We improve the LP-relative approximation ratio to $1.55576$. Our main contribution is a new bound on the cost of parity correction that exploits parity information revealed by further pruning in the analysis. This bound makes the splitting-off preprocessing unnecessary, so the improvement is achieved by a simpler version of their algorithm. The stated factor follows from a numerical parameter search with exact verification, while an elementary analysis already yields an LP-relative $1.56$-approximation.

arXiv comment20 pages, 2 figures