Approximating Prize-Collecting Variants of TSP

Morteza Alimi, Tobias Mömke, Michael Ruderer

We present an approximation algorithm for the Prize-collecting Ordered Traveling Salesman Problem (PCOTSP), which simultaneously generalizes the Prize-collecting TSP and the Ordere…