About the EventSurvivable network design (SND) is a suite of algorithmic problems that focus on designing minimum cost networks satisfying desired robustness characteristics. Over the last decade, networking technology has gradually embraced wireless infrastructure, where a substantial fraction of the deployment cost comes from network nodes (e.g. cellular base stations). This motivates us to generalize the traditional edgeweighted cost model in SND problems to one that is able to handle fixed or variable costs on nodes as well. In this talk, I will present two sets of SND problems that attempt to bridge this gap.
In the first part of the talk, I will give the first polylogarithmic competitive algorithm for the online steiner tree problem with node and edge costs. This is joint work with Seffi Naor and Mohit Singh, and appeared in FOCS 2011. In the second part of the talk, I will introduce a new suite of SND problems called network activation problems that generalize node costs and several other previously studied cost models. In these problems, instead of a fixed cost at a node, the algorithm designer must choose the cost that she wants to pay at a node, and the activation of a link depends on the cost paid at its two endpoints. I will give approximation algorithms and (matching) hardness results for several wellstudied SND problems in this framework. These results appeared in SODA 2011.
