Combinatorial Optimization Reading Group - Ishan Bansal

Title: The Capacitated Survivable Network Design Problem

Abstract:

The Capacitated Survivable Network Design Problem or Cap-SNDP models a network reinforcement problem where the network designer wants to find a minimum-cost set of reinforcements that protects the network from an adversary. The first half of this talk will be based on work by Carr, Fleischer, Leung, Philips who provide a $\beta +1$ approximation algorithm for this MAXSNP-hard problem where $\beta$ is the maximum size of a minimal cut in the underlying network. The rest of the talk will be based on joint work with Swamy and Koenemann who provide an $O((\log{\log{\beta}})^2)$ approximation algorithm for the Cap-SNDP on outerplanar graphs.