Combining Approximation Algorithms for the Prize-Collecting TSP

2009/10/03 by Michel X. Goemans, Goemans, Michel X.
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Vehicle Routing Optimization Methods #cs.DS

paper · pdf · doi:10.48550/arxiv.0910.0553

5 pages

arxiv created 2009/10/03 · arxiv updated 2009/12/01

Abstract

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.

Related

• Approximating Prize-Collecting Variants of TSP
• A Better-Than-1.6-Approximation for Prize-Collecting TSP
• 5/4 approximation for Symmetric TSP
• A Randomized Rounding Algorithm for the Asymmetric Traveling Salesman Problem
• An improved approximation guarantee for Prize-Collecting TSP