Very Sparse Additive Spanners and Emulators
Greg Bodwin, Virginia Vassilevska Williams · 2015
We obtain new upper bounds on the additive distortion for graph emulators and spanners on relatively few edges. We introduce a new subroutine called "strip creation," and we combine this subroutine with several other ideas to obtain the following results: