In this paper, we present a new approach of creating PTAS to the TSP problems by defining a bounded-curvature surface embedded spaces. Using this definition we prove: - A bounded-curvature surface embedded spaces TSP admits to a PTAS. - Every bounded doubling dimension space can be embedded into a bounded-curvature surface. - Every uniform metric space can be embedded into a bounded-curvature surface. Thus, the algorithm generalizes arXiv:1112.0699 (and therefore [7] and [8] as well, w.r.t PTAS of TSP). But, the algorithm is much broader as uniform metric spaces aren't bounded doubling dimension spaces. It should be mentioned that our definition of a surface is derived from Riemannian geometry, but doesn't match it exactly. therefore, our definitions and basic geometry algorithm is given here in full. [7] Sanjeev Arora. 1998. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 5 (September 1998), 753-782. DOI=http://dx.doi.org/10.1145/290179.290180 [8] Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial time approximation scheme for geometric TSP, k- MST, and related problems. SIAM J. Comput., 28(4):1298-1309, 1999.
翻译:在本文中,我们提出了一个为TSP问题创建 PTAS的新方法,方法是定义一个受约束的精度表面嵌入空间。我们用这个定义可以证明: - 一个受约束的精度表面嵌入空间 TSP 承认一个受约束的表面嵌入空间 。 每个受约束的双维空间都可以嵌入一个受约束的精度表面 。 因此,每一个统一的测量空间都可以嵌入一个受约束的精度表面。 因此,算法将Arxiv:11122.0699(因此[7]和[8],以及TSP的硬度表面嵌入空间 。 但是,算法的范围要大得多,因为统一的测量空间并不是受约束的双层空间 。应该提到,我们对表面的定义来自里曼的精度表面,但并不完全吻合。 因此,我们的定义和基本的测地算算法可以完全嵌入一个受约束的精度表面表面。 [7 Sanjeev Arora. 1998, 用于Eucliidean 巡回销售员和其他测问题的精确时间接近计划。 JCM. 80-401, J.