Online Network Design Algorithms via Hierarchical Decompositions

In this talk, I will present a new analysis framework for network design and show how it leads to improved competitive ratios for several online problems. At the heart of this framework is a charging scheme based on embedding into hierarchically well-separated trees. Using our framework, we develop the first deterministic algorithms that achieve the optimal (up to constants) competitive ratios for the multi-commodity rent-or-buy, connected facility location, and Steiner network (with edge duplication) problems. Our algorithms are simple greedy algorithms that do not compute the embedding. We also obtain simpler analysis of previous algorithms for other problems.