ISSN:
1436-4646
Keywords:
Linear programming
;
prize collecting
;
rounding fractional solutions
;
traveling salesman problem
;
worst-case analysis
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01581256
Permalink
