A note on the prize collecting traveling salesman problem (Q687042): Difference between revisions

The authors are dealing with the following problem: given an undirected graph \(G(V,E)\) with a cost function \(c(e)\) on the edge set \(E\) and a penalty function \(\pi(v)\) on the set \(V\) of vertices; find a subtour, such that the length of the tour plus the sum of the penalties of all those vertices, which are not visited in this tour, is minimal. Additionally, it is assumed that the edge costs satisfy the triangle inequality. The paper presents an approximation algorithm with guaranteed approximation ratio 2,5. Unlike the Christofides heuristic in the usual traveling salesman problem, this algorithm is not of combinatorial nature but uses the ellipsoid method to solve a set of specific LP-relaxations (for each vertex \(v\in V\), where \(v\) has to be visited) and finally the best of the induced feasible solutions of the original problem is chosen.