论文标题
用于估计MST和TSP总体成本的下级算法和下限
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics
论文作者
论文摘要
我们考虑了跨金属空间和查询复杂性算法的设计，用于估计最低跨度树（MST）的成本以及最低旅行推销员（TSP）巡回演出的成本，以$ n $ n $点的计量。我们首先考虑$ o（n）$ - 空间制度，并表明，当输入是该度量的所有$ \ binom {n} {2} $条目的所有$ \ binom {n} {2} $条目时，对于任何$α\ ge 2 $，MST和TSP的成本都可以是$ a $ approxim-appproxim-使用$ \ tilde is Space {o/y/$α（n/al），以及那2 $ n $ al/al $α（n 2 $），以及n 2 $ and $α（n 2 $），以及此任务所需的。此外，我们表明，即使允许流算法$ p $通过公制流，它仍然需要$ \tildeΩ（\ sqrt {n/αp^2}）$ space。 接下来，我们考虑半流制度，即使确切的MST成本都很容易计算，主要挑战是将TSP成本估算为严格高于$ 2 $的因素。我们表明，如果输入是诱导基础度量的加权图的所有边缘的流，则对于任何$ \ varepsilon> 0 $，任何一个pass $（2- \ varepsilon）$ - tsp成本的近似 - 需要$ω（\ varepsilon^2 n^2）$空间；另一方面，有一个$ \ tilde {o}（n）$ space两通算法，该算法将TSP的成本近似于1.96倍。 最后，我们考虑将公制TSP成本估算到严格比$ 2 $的因素的查询复杂性，当时该算法可以访问矩阵，该矩阵指定了所有点之间的成对距离。对于此模型中的MST估计，众所周知，使用$ \ tilde {o}（n/\ varepsilon^{o（1）}）$ queries可以实现$（1+ \ varepsilon）$ - 近似值。我们设计了一种算法，该算法执行$ \ tilde {o}（n^{1.5}）$ ganding查询，并且当已知指标中包含以重量支撑的跨度为单位的树时，严格地实现了比$ 2 $ - approximation的要好得多。
We consider the design of sublinear space and query complexity algorithms for estimating the cost of a minimum spanning tree (MST) and the cost of a minimum traveling salesman (TSP) tour in a metric on $n$ points. We first consider the $o(n)$-space regime and show that, when the input is a stream of all $\binom{n}{2}$ entries of the metric, for any $α\ge 2$, both MST and TSP cost can be $α$-approximated using $\tilde{O}(n/α)$ space, and that $Ω(n/α^2)$ space is necessary for this task. Moreover, we show that even if the streaming algorithm is allowed $p$ passes over a metric stream, it still requires $\tildeΩ(\sqrt{n/αp^2})$ space. We next consider the semi-streaming regime, where computing even the exact MST cost is easy and the main challenge is to estimate TSP cost to within a factor that is strictly better than $2$. We show that, if the input is a stream of all edges of the weighted graph that induces the underlying metric, for any $\varepsilon > 0$, any one-pass $(2-\varepsilon)$-approximation of TSP cost requires $Ω(\varepsilon^2 n^2)$ space; on the other hand, there is an $\tilde{O}(n)$ space two-pass algorithm that approximates the TSP cost to within a factor of 1.96. Finally, we consider the query complexity of estimating metric TSP cost to within a factor that is strictly better than $2$, when the algorithm is given access to a matrix that specifies pairwise distances between all points. For MST estimation in this model, it is known that a $(1+\varepsilon)$-approximation is achievable with $\tilde{O}(n/\varepsilon^{O(1)})$ queries. We design an algorithm that performs $\tilde{O}(n^{1.5})$ distance queries and achieves a strictly better than $2$-approximation when either the metric is known to contain a spanning tree supported on weight-$1$ edges or the algorithm is given access to a minimum spanning tree of the graph.
