pith. sign in

arxiv: 0910.0553 · v1 · submitted 2009-10-03 · 💻 cs.DS

Combining Approximation Algorithms for the Prize-Collecting TSP

Michel X. Goemans This is my paper
classification 💻 cs.DS
keywords algorithmapproximationcombiningprize-collectingalgorithmsbienstockgoemansobtained
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Approximation algorithms for the prize-collecting rural postman problem

    cs.DS 2026-05 conditional novelty 7.0

    A new algorithm approximates the prize-collecting rural postman problem within a factor strictly less than 1.6 and proves a 2-approximation barrier for PCTSP reductions.

  2. Reducing Prize-Collecting Stroll and Related Routing Problems to Prize-Collecting TSP

    cs.DS 2026-06 unverdicted novelty 6.0

    Reduction from prize-collecting-Φ-TSP to prize-collecting TSP yields (ρ + ε)-approximations for constant prescribed vertices, improving the prize-collecting stroll guarantee to better than 1.6 from 1.6662.