The 4/3 Additive Spanner Exponent Is Tight
The 4/3 Additive Spanner Exponent Is Tight
A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of a spanner and the quality of its approximation, so long as distance error is measured multiplicatively . A central open …