Haifa University - Dept. of CS Theory Seminar

Speaker : Shai Solomon, Ben-Gurion University.

Title: "Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners".

Date: Thursday, June 5.

Place: Haifa U. Education Building, room 566.

Time: 12:15 - 13:30

Abstract:

We show that for every n-point metric space M and positive
integer k=O(log n), there exists a spanning tree T with unweighted
diameter O(k) and weight w(T) = O(k \cdot n^{1/k}) * w(MST(M)),
and a spanning tree T' with weight w(T') =
O(k) * w(MST(M)) and unweighted diameter O(k *  n^{1/k}).
Moreover, there is a designated point rt such that for
every other point v$, both dist_T(rt,v) and dist_{T'}(rt,v) are
at most (1+\eps) * dist_M(rt,v), for an arbitrarily small
constant \epsilon > 0. These trees also achieve an optimal maximum
degree. Furthermore, we demonstrate that these trees can be
constructed efficiently.

We prove that these tradeoffs between unweighted diameter and weight
are **tight up to constant factors** in the entire range of
parameters. Moreover, our lower bounds apply to a basic
one-dimensional Euclidean space.

Our lower bounds for the particular case of unweighted diameter
O(log n) are of independent interest, settling a long-standing
open problem in Computational Geometry. In STOC'95 Arya et al.
devised a construction of Euclidean Spanners with unweighted
diameter O(log n) and weight O(log n) * w(MST(M)). In
SODA'05 Agarwal et al. showed that this result is tight up to a
factor of O(log log n). We close this gap and show that the
result of Arya et al. is tight up to constant factors.

Finally, our upper bounds imply improved approximation algorithms
for the **minimum h-hop  spanning tree** and **bounded
diameter minimum spanning tree** problems for metric spaces.

Joint work with Yefim Dinitz and Michael Elkin.