A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics

T-H. Hubert Chan, Haotian Jiang, Shaofeng H. -C. Jiang

We present a unified polynomial-time approximation scheme (PTAS) for the prize collecting traveling salesman problem (PCTSP) and the prize collecting Steiner tree problem (PCSTP) i…