Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation
Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation
复制标题
DOI：
10.4230/lipics.icalp.2020.30
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Yu Chen;Sampath Kannan;S. Khanna
中科院分区：
文献类型：
--
作者：
Yu Chen;Sampath Kannan;S. Khanna
我们考虑设计均值时间算法的问题，以估计最低度量旅行者（TSP）巡回演出的成本。具体而言，给定指定$ n $ n $ d $ d $ d $ d $的访问权限在$ n $点之间，目标是通过仅执行sublinear（大小为$ d $）查询来估算TSP成本。对于估计度量最小跨越树（MST）的重量密切相关的问题，众所周知，对于任何$ \ varepsilon> 0 $，都存在$ \ tilde {o}（n/\ varepsilon^{o（o） 1）}）$ time算法，该算法返回$（1 + \ varepsilon）$ - MST成本的近似估计。该结果立即意味着$ \ tilde {o}（n/\ varepsilon^{o（1）}）$ time算法，以估算$（2 + \ varepsilon）$ actor的TSP成本，用于任何$ \ VAREPSILON> 0 $。但是，已知没有$ O（n^2）$时间算法将公制TSP近似于严格高于$ 2 $的因素。另一方面，也没有许多已知的障碍可以排除$（1 + \ varepsilon）$ - 带有$ \ tilde {o}（n）$时间的公制tsp的近似估计算法，任何固定的$ \ varepsilon时间> 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.