Combining Approximation Algorithms for the Prize-Collecting TSP
Goemans, Michel X.
Original · EN
We present a 1.91457-approximation algorithm for the prize-collecting travelling salesman problem. This is obtained by combining a randomized variant of a rounding algorithm of Bienstock et al. and a primal-dual algorithm of Goemans and Williamson.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.