Seeun Umboh
I will present a new approach for network design, and apply it to obtain the best possible (up to constants) competitive ratios for several online problems. At the heart of this work is an analysis framework based on embeddings into hierarchically well-separated trees (HSTs). Our approach yields simple greedy algorithms and straightforward analyses. Unlike the usual algorithmic application of tree embeddings, the embeddings are used only for the analysis, not in the algorithms.
This talk is based on an upcoming SODA15 paper; a preprint is available at http://arxiv.org/abs/1410.4240