doubling metrics

A PTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics

  • T-H. Hubert Chan
  • Shaofeng H.-C. Jiang
    • Categories Approximation Algorithms Tags , , ,

    We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a given collection of subsets (regions or neighborhoods) in the underlying metric space. We give a randomized polynomial time approximation scheme (PTAS) when the regions are fat weakly disjoint. This notion … Read more