OFER NEIMAN

An (α,β)-spanner of a weighted graph G=(V,E), is a subgraph H such that for every u,v∈V, d_G(u,v)≤d_H(u,v)≤α·d_G(u,v)+β. The main parameters of interest for spanners are their size (number of edges) and their lightness (the ratio between the total weight of H to the weight of a minimum spanning tree). In this paper we focus on near-additive spanners, where α=1+ε for arbitrarily small ε>0. We show the first construction of light spanners in this setting. Specifically, for any integer parameter k≥1, we obtain an (1+ε,O(k/ε)^k·W(·,·))-spanner with lightness O~(n^1/k) (where W(·,·) indicates for every pair u,v∈V the heaviest edge in some shortest path between u, v). In addition, we can also bound the number of edges in our spanner by O(kn^1+3/k).