A hierarchy of lower bounds for sublinear additive spanners
Amir Abboud, Greg Bodwin, Seth Pettie · Symposium on Discrete Algorithms · 2017
Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say O(n1+δ) bits. There is an inherent tradeoff between the sparsity parameter δ and the stretch function f of the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem.It has been known for some time that when δ ≥ 1/3 there are schemes with constant additive stretch (distance d is stretched to at most f(d) = d + O(1)), and recent results of Abboud and Bodwin show that when δ