Debmalya Panigrahi: Survivable Network Design with Node and Edge Costs

Survivable 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 edge-weighted 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 poly-logarithmic 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 end-points. I will give approximation algorithms and (matching) hardness results for several well-studied SND problems in this framework. These results appeared in SODA 2011.