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/

Zendy Plus

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

Zendy Tools

Zendy Open

Spanners for low dimensional spaces (e.g. Euclidean space of constantdimension, or doubling metrics) are well understood. This lies in contrast tothe situation in high dimensional spaces, where except for the work ofHar-Peled, Indyk and Sidiropoulos (SODA 2013), who showed that any $n$-pointEuclidean metric has an $O(t)$-spanner with $\tilde{O}(n^{1+1/t^2})$ edges,little is known.  In this paper we study several aspects of spanners in high dimensional normedspaces. First, we build spanners for finite subsets of $\ell_p$ with $1<p\le2$. Second, our construction yields a spanner which is both sparse and also{\em light}, i.e., its total weight is not much larger than that of the minimumspanning tree. In particular, we show that any $n$-point subset of $\ell_p$ for$1<p\le 2$ has an $O(t)$-spanner with $n^{1+\tilde{O}(1/t^p)}$ edges andlightness $n^{\tilde{O}(1/t^p)}$.  In fact, our results are more general, and they apply to any metric spaceadmitting a certain low diameter stochastic decomposition. It is known thatarbitrary metric spaces have an $O(t)$-spanner with lightness $O(n^{1/t})$. Weexhibit the following tradeoff: metrics with decomposability parameter$\nu=\nu(t)$ admit an $O(t)$-spanner with lightness $\tilde{O}(\nu^{1/t})$. Forexample, $n$-point Euclidean metrics have $\nu\le n^{1/t}$, metrics withdoubling constant $\lambda$ have $\nu\le\lambda$, and graphs of genus $g$ have$\nu\le g$. While these families do admit a ($1+\epsilon$)-spanner, itslightness depend exponentially on the dimension (resp. $\log g$). Ourconstruction alleviates this exponential dependency, at the cost of incurringlarger stretch.

Light Spanners for High Dimensional Norms via Stochastic Decompositions