paper

Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics

arXiv:2203.14798

Abstract

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 $(2 n)$ entries of the metric, for any $I^\pm \geq 2$ , both MST and TSP cost can be $I^\pm$ -approximated using $O ~ (n / I^\pm)$ space, and that $I^c ◯ (n / I^\pm^{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 $I^~ c ◯ (n / I^\pm 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 $ε > 0$ , any one-pass $(2 - ε)$ -approximation of TSP cost requires $I^c ◯ (ε^{2} n^{2})$ space; on the other hand, there is an $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 + ε)$ -approximation is achievable with $O ~ (n / ε^{O (1)})$ queries. We design an algorithm that performs $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.