Improved method cuts route plus penalty cost for prize collecting tsp
Approximating Prize-Collecting TSP below 1.556
Data Structures and Algorithms
Summary
The prize-collecting traveling salesperson problem involves planning a trip that visits some places while skipping others by paying a penalty. The goal is to minimize the trip length plus the penalty cost. The paper shows that a simpler version of a recent algorithm performs better than before, achieving a better approximation to the best possible route. This improvement comes from better understanding a step that fixes route properties in the solution.
What this means in practice
- •For logistics planners: Generate more cost-effective routes that balance travel distance and penalties for skipped stops using improved approximation methods.
- •For network schedulers: Enhance scheduling of data collection or maintenance tasks with flexible visitation requirements by applying tighter cost approximations.
Authors
Hong Li
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. We show that a simpler version of their algorithm, obtained by omitting the splitting-off preprocessing before the tree decomposition, has an LP-relative approximation ratio of $1.555761$. The improvement comes from a stronger analysis of the parity-correction step.