|
|||||
|
|
A note on the prize collecting traveling salesman problem |
|
| Authors: | Daniel Bienstock Michel X Goemans David Simchi-Levi David Williamson |
| Institution: | (1) Department of Industrial Engineering and Operations Research, Columbia University in the City of New York, 10027-6699 New York, NY, USA;(2) Department of Mathematics, MIT, Cambridge, MA, USA;(3) Department of Industrial Engineering and Operations Research, Columbia University, New York, USA;(4) Laboratory for Computer Science, MIT, Cambridge, MA, USA |
| Abstract: | We 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. We 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.Research supported in part by ONR contract N00014-90-J-1649 and NSF contract DDM-8922712. |
| Keywords: | Linear programming prize collecting rounding fractional solutions traveling salesman problem worst-case analysis |
| 本文献已被 SpringerLink 等数据库收录！ | |