collaborators

1 paper

cs.DS2025

A Better-Than-1.6-Approximation for Prize-Collecting TSP

Jannis Blauth, Nathan Klein, Martin Nägele

Prize-Collecting TSP is a variant of the traveling salesperson problem where one may drop vertices from the tour at the cost of vertex-dependent penalties. The quality of a solutio…