Filtser, Arnold ;
Neiman, Ofer
Light Spanners for High Dimensional Norms via Stochastic Decompositions
Abstract
Spanners for low dimensional spaces (e.g. Euclidean space of constant dimension, or doubling metrics) are well understood. This lies in contrast to the situation in high dimensional spaces, where except for the work of HarPeled, Indyk and Sidiropoulos (SODA 2013), who showed that any npoint Euclidean metric has an O(t)spanner with O~(n^{1+1/t^2}) edges, little is known.
In this paper we study several aspects of spanners in high dimensional normed spaces. First, we build spanners for finite subsets of l_p with 1<p <=2. Second, our construction yields a spanner which is both sparse and also light, i.e., its total weight is not much larger than that of the minimum spanning tree. In particular, we show that any npoint subset of l_p for 1<p <=2 has an O(t)spanner with n^{1+O~(1/t^p)} edges and lightness n^{O~(1/t^p)}.
In fact, our results are more general, and they apply to any metric space admitting a certain low diameter stochastic decomposition. It is known that arbitrary metric spaces have an O(t)spanner with lightness O(n^{1/t}). We exhibit the following tradeoff: metrics with decomposability parameter nu=nu(t) admit an O(t)spanner with lightness O~(nu^{1/t}). For example, npoint Euclidean metrics have nu <=n^{1/t}, metrics with doubling constant lambda have nu <=lambda, and graphs of genus g have nu <=g. While these families do admit a (1+epsilon)spanner, its lightness depend exponentially on the dimension (resp. log g). Our construction alleviates this exponential dependency, at the cost of incurring larger stretch.
BibTeX  Entry
@InProceedings{filtser_et_al:LIPIcs:2018:9492,
author = {Arnold Filtser and Ofer Neiman},
title = {{Light Spanners for High Dimensional Norms via Stochastic Decompositions}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {29:129:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9492},
URN = {urn:nbn:de:0030drops94922},
doi = {10.4230/LIPIcs.ESA.2018.29},
annote = {Keywords: Spanners, Stochastic Decompositions, High Dimensional Euclidean Space, Doubling Dimension, Genus Graphs}
}
14.08.2018
Keywords: 

Spanners, Stochastic Decompositions, High Dimensional Euclidean Space, Doubling Dimension, Genus Graphs 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

14.08.2018 