New additive spanners
Shiri Chechik · Symposium on Discrete Algorithms · 2013
This paper considers additive and purely additive spanners. We present a new purely additive spanner of size O(n7/5) with additive stretch 4. This construction fills in the gap between the two existing constructions for purely additive spanners, one for 2-additive spanner of size O(n3/2) and the other for 6-additive spanner of size O(n4/3), and thus answers a main open question in this area. In addition, we present a construction for additive spanners with O(n1+δ) edges and additive stretch of O(n1/2−3δ/2) for any 3/17 ≤ δ