论文标题
标准TSP成本估算的下级算法和下限
Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation
论文作者
论文摘要
我们考虑设计均值时间算法的问题，以估计最低度量旅行者（TSP）巡回演出的成本。具体而言，给定指定$ n $ n $ d $ d $ d $ d $的访问权限在$ n $点之间，目标是通过仅执行sublinear（大小为$ d $）查询来估算TSP成本。对于估计度量最小跨树（MST）的重量密切相关的问题，众所周知，对于任何$ \ varepsilon> 0 $，都存在$ \ tilde {o}（n/\ varepsilon^{o（o（1））$ time algorithm返回$（1 + \ varepsilon）$ - \ varepsiLOn）。该结果立即意味着$ \ tilde {o}（n/\ varepsilon^{o（1）}）$ time算法，以估算$（2 + \ varepsilon）$ actor的TSP成本在任何$ \ varepsilon> 0 $中。但是，已知没有$ O（n^2）$时间算法将公制TSP近似于严格高于$ 2 $的因素。另一方面，也没有已知的障碍可以排除$（1 + \ varepsilon）$的存在 - 用于公制TSP的近似估计算法，$ \ tilde {o}（n）$时间用于任何固定$ \ varepsilon> 0 $ 0 $。在本文中，我们在算法和下限方面取得了进展，以估计公制TSP成本。我们还表明，估计公制TSP成本的问题与估计图中最大匹配的大小的问题紧密相关。
We consider the problem of designing sublinear time algorithms for estimating the cost of a minimum metric traveling salesman (TSP) tour. Specifically, given access to a $n \times n$ distance matrix $D$ that specifies pairwise distances between $n$ points, the goal is to estimate the TSP cost by performing only sublinear (in the size of $D$) queries. For the closely related problem of estimating the weight of a metric minimum spanning tree (MST), it is known that for any $\varepsilon > 0$, there exists an $\tilde{O}(n/\varepsilon^{O(1)})$ time algorithm that returns a $(1 + \varepsilon)$-approximate estimate of the MST cost. This result immediately implies an $\tilde{O}(n/\varepsilon^{O(1)})$ time algorithm to estimate the TSP cost to within a $(2 + \varepsilon)$ factor for any $\varepsilon > 0$. However, no $o(n^2)$ time algorithms are known to approximate metric TSP to a factor that is strictly better than $2$. On the other hand, there were also no known barriers that rule out the existence of $(1 + \varepsilon)$-approximate estimation algorithms for metric TSP with $\tilde{O}(n)$ time for any fixed $\varepsilon > 0$. In this paper, we make progress on both algorithms and lower bounds for estimating metric TSP cost. We also show that the problem of estimating metric TSP cost is closely connected to the problem of estimating the size of a maximum matching in a graph.
