Center for Algorithms and Theory of Computation

CS 269S, Spring 2019: Theory Seminar
Bren Hall, Room 1423, 1pm


May 10, 2019:

Greedy spanners are optimal in doubling metrics

Hadi Khodabandeh

We show that the greedy spanner algorithm constructs a (1+ϵ)-spanner of weight ϵ−O(d)w(MST) for a point set in metrics of doubling dimension d, resolving an open problem posed by Gottlieb. Our result generalizes the result by Narasimhan and Smid who showed that a point set in d-dimension Euclidean space has a (1+ϵ)-spanner of weight at most ϵ−O(d)w(MST). Our proof only uses the packing property of doubling metrics and thus implies a much simpler proof for the same result in Euclidean space.

(Based on a paper by Glencora Borradaile, Hung Le, and Christian Wulff-Nilsen)