text: 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 Har-Peled, Indyk and Sidiropoulos (SODA 2013), who showed that any @math -point Euclidean metric has an @math -spanner with @math 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 @math with @math . 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 @math -point subset of @math for @math has an @math -spanner with @math edges and lightness @math . 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 @math -spanner with lightness @math . We exhibit the following tradeoff: metrics with decomposability parameter @math admit an @math -spanner with lightness @math . For example, @math -point Euclidean metrics have @math , metrics with doubling constant @math have @math , and graphs of genus @math have @math . While these families do admit a ( @math )-spanner, its lightness depend exponentially on the dimension (resp. @math ). Our construction alleviates this exponential dependency, at the cost of incurring larger stretch.
  @cite_30: Given a graphG, a subgraphG' is at-spanner ofG if, for everyu,v ?V, the distance fromu tov inG' is at mostt times longer than the distance inG. In this paper we give a simple algorithm for constructing sparse spanners for arbitrary weighted graphs. We then apply this algorithm to obtain specific results for planar graphs and Euclidean graphs. We discuss the optimality of our results and present several nearly matching lower bounds.
  @cite_41: 
  @cite_29: We show that the greedy spanner algorithm constructs a @math -spanner of weight @math for a point set in metrics of doubling dimension @math , resolving an open problem posed by Gottlieb. Our result generalizes the result by Narasimhan and Smid who showed that a point set in @math -dimension Euclidean space has a @math -spanner of weight at most @math . Our proof only uses the packing property of doubling metrics and thus implies a much simpler proof for the same result in Euclidean space.
  @cite_3: 
  @cite_2: 
  @cite_66: Let G = (V,E) be an undirected weighted graph with vVv = n and vEv = m. Let k ≥ 1 be an integer. We show that G = (V,E) can be preprocessed in O(kmn1 k) expected time, constructing a data structure of size O(kn1p1 k), such that any subsequent distance query can be answered, approximately, in O(k) time. The approximate distance returned is of stretch at most 2k−1, that is, the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and 2k−1. A 1963 girth conjecture of Erdos, implies that Ω(n1p1 k) space is needed in the worst case for any real stretch strictly smaller than 2kp1. The space requirement of our algorithm is, therefore, essentially optimal. The most impressive feature of our data structure is its constant query time, hence the name "oracle". Previously, data structures that used only O(n1p1 k) space had a query time of Ω(n1 k).Our algorithms are extremely simple and easy to implement efficiently. They also provide faster constructions of sparse spanners of weighted graphs, and improved tree covers and distance labelings of weighted or unweighted graphs.
  @cite_20: 
  @cite_4: 
  @cite_60: 
  @cite_7: 
  @cite_70: 
  @cite_28: 
  @cite_84: 
  @cite_79: 
  @cite_27: The greedy spanner is arguably the simplest and most well-studied spanner construction. Experimental results demonstrate that it is at least as good as any other spanner construction, in terms of both the size and weight parameters. However, a rigorous proof for this statement has remained elusive. In this work we fill in the theoretical gap via a surprisingly simple observation: The greedy spanner is (or existentially near-optimal) for several important graph families. Focusing on the weight parameter, the state-of-the-art spanner constructions for both general graphs (due to Chechik and Wulff-Nilsen [SODA'16]) and doubling metrics (due to Gottlieb [FOCS'15]) are complex. Plugging our observation on these results, we conclude that the greedy spanner achieves near-optimal weight guarantees for both general graphs and doubling metrics, thus resolving two longstanding conjectures in the area. Further, we observe that approximate-greedy algorithms are existentially near-optimal as well. Consequently, we provide an @math -time construction of @math -spanners for doubling metrics with constant lightness and degree. Our construction improves Gottlieb's construction, whose runtime is @math and whose number of edges and degree are unbounded, and remarkably, it matches the state-of-the-art Euclidean result (due to [SICOMP'02]) in all the involved parameters (up to dependencies on @math and the dimension).
  @cite_19: 
  @cite_34: 
  @cite_14: 
  @cite_65: Thorup and Zwick showed that for any integer k≥ 1, it is possible to preprocess any positively weighted undirected graph G=(V,E), with |E|=m and |V|=n, in O(kmn @math ) expected time and construct a data structure (a (2k–1)-approximate distance oracle) of size O(kn @math ) capable of returning in O(k) time an approximation @math of the distance δ(u,v) from u to v in G that satisfies @math , for any two vertices u,v∈ V. They also presented a much slower O(kmn) time deterministic algorithm for constructing approximate distance oracle with the slightly larger size of O(kn @math log n). We present here a deterministic O(kmn @math ) time algorithm for constructing oracles of size O(kn @math ). Our deterministic algorithm is slower than the randomized one by only a logarithmic factor. Using our derandomization technique we also obtain the first deterministic linear time algorithm for constructing optimal spanners of weighted graphs. We do that by derandomizing the O(km) expected time algorithm of Baswana and Sen (ICALP’03) for constructing (2k–1)-spanners of size O(kn @math ) of weighted undirected graphs without incurring any asymptotic loss in the running time or in the size of the spanners produced.
  @cite_0: Given as input an edge-weighted graph, we analyze two algorithms for finding subgraphs with low total edge weight. The first algorithm finds a separator subgraph with a small number of components, and is analyzed for graphs with an arbitrary excluded minor. The second algorithm finds a spanner with small stretch factor, and is analyzed for graphs in a hereditary family G(k). These results imply (i) a QPTAS (quasi-polynomial time approximation scheme) for the TSP (traveling salesperson problem) in unweighted graphs with an excluded minor, and (ii) a QPTAS for the TSP in weighted graphs with bounded genus.
summary: In addition to the results mentioned above, sparse light spanners with small stretch were studied also for: planar graphs @cite_30 @cite_84 , apex graphs @cite_3 , bounded pathwidth graphs @cite_14 @cite_70 , bounded treewidth graphs @cite_28 @cite_70 , and graphs excluding fixed minors @cite_0 @cite_28 @cite_29 . From the algorithmic perspective, there is a rich study of efficient spanners construction @cite_66 @cite_34 @cite_65 @cite_79 @cite_20 @cite_7 @cite_60 @cite_4 @cite_2 @cite_41 @cite_27 @cite_19 .