Fall 2015

Fine Design Seminar Series

Sep 22, 2015 11:00 am – 12:30 pm 

Add to Calendar


Seeun William Umboh (Technische Universiteit Eindhoven)


Calvin Lab Room 116

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.