| Article ID: | iaor19941972 |
| Country: | Netherlands |
| Volume: | 59 |
| Issue: | 3 |
| Start Page Number: | 413 |
| End Page Number: | 420 |
| Publication Date: | May 1993 |
| Journal: | Mathematical Programming (Series A) |
| Authors: | Bienstock Daniel, Goemans Michel X., Simchi-Levi David, Williamson David |
The authors study the version of the prize collecting traveling salesman problem, where the objective is to find a tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. They present an approximation algorithm with constant bound. The algorithm is based on Christofides’ algorithm for the traveling salesman problem as well as a method to round fractional solutions of a linear programming relaxation to integers, feasible for the original problem.