Speaker
Description
Shimon Kogan and Merav Parter
Abstract: The only known upper bound for this problem is given by an implicit construction of
[Pettie, ICALP 2007] that provides a linear-size emulator with $+\widetilde{O}(n^{1/4})$ stretch. No improvement on this problem has been shown since then.
In this work we improve upon the long standing additive stretch of $\widetilde{O}(n^{1/4})$, by presenting constructions of linear-size emulators with $\widetilde{O}(n^{0.222})$ additive stretch. Our constructions improve the state-of-the-art size vs.\ stretch tradeoff in the entire regime. For example, for every $\epsilon >1/7$, we provide $+n^{f(\epsilon)}$ emulators of size $\widetilde{O}(n^{1+\epsilon})$, for $f(\epsilon)=1/5-3\epsilon/5$. This should be compared with the current bound of $f(\epsilon)=1/4-3\epsilon/4$ by [Pettie, ICALP 2007].
The new emulators are based on an extended and optimized toolkit for computing weighted additive emulators with sublinear distance error. Our key construction provides a weighted modification of the well-known Thorup and Zwick emulators [SODA 2006]. We believe that this TZ variant might be of independent interest, especially for providing improved stretch for distant pairs.