论文标题
在固定加倍维度的度量空间中，最大旅行推销员问题的有效PTA
Efficient PTAS for the Maximum Traveling Salesman Problem in a Metric Space of Fixed Doubling Dimension
论文作者
论文摘要
最大旅行人员问题（最大tsp）包括找到一个汉密尔顿周期，在给定的完整加权图中边缘的总重量最大。在一般度量案例中，此问题是APX的，但在几何近似设置中接受多项式时间近似方案，当边缘重量在固定维真实空间中由矢量规范诱导时。我们在固定加倍尺寸的任意度量空间中提出了最大TSP的第一个近似方案。所提出的算法实现了有效的PTA，对于任何固定的$ \ varepsilon \ in（0,1）$中的任何固定的PTA，计算$（1- \ varepsilon）$ - 在立方体时间内对问题的近似解决方案。此外，我们建议一种立方时算法，该算法在固定和subogarithmic倍增尺寸中发现公表示最大tsp的最佳解决方案。
The maximum traveling salesman problem (Max TSP) consists of finding a Hamiltonian cycle with the maximum total weight of the edges in a given complete weighted graph. This problem is APX-hard in the general metric case but admits polynomial-time approximation schemes in the geometric setting, when the edge weights are induced by a vector norm in fixed-dimensional real space. We propose the first approximation scheme for Max TSP in an arbitrary metric space of fixed doubling dimension. The proposed algorithm implements an efficient PTAS which, for any fixed $\varepsilon\in(0,1)$, computes a $(1-\varepsilon)$-approximate solution of the problem in cubic time. Additionally, we suggest a cubic-time algorithm which finds asymptotically optimal solutions of the metric Max TSP in fixed and sublogarithmic doubling dimensions.
