English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the design of sublinear space and query complexity algorithms forestimating the cost of a minimum spanning tree (MST) and the cost of a minimumtraveling 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 $\alpha \ge 2$, both MST and TSPcost can be $\alpha$-approximated using $\tilde{O}(n/\alpha)$ space, and that$\Omega(n/\alpha^2)$ space is necessary for this task. Moreover, we show thateven if the streaming algorithm is allowed $p$ passes over a metric stream, itstill requires $\tilde{\Omega}(\sqrt{n/\alpha p^2})$ space.  We next consider the semi-streaming regime, where computing even the exactMST cost is easy and the main challenge is to estimate TSP cost to within afactor that is strictly better than $2$. We show that, if the input is a streamof all edges of the weighted graph that induces the underlying metric, for any$\varepsilon > 0$, any one-pass $(2-\varepsilon)$-approximation of TSP costrequires $\Omega(\varepsilon^2 n^2)$ space; on the other hand, there is an$\tilde{O}(n)$ space two-pass algorithm that approximates the TSP cost towithin a factor of 1.96.  Finally, we consider the query complexity of estimating metric TSP cost towithin a factor that is strictly better than $2$, when the algorithm is givenaccess to a matrix that specifies pairwise distances between all points. ForMST 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 treesupported on weight-$1$ edges or the algorithm is given access to a minimumspanning tree of the graph.

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