Approximating 2-Edge-Connected Network Design Problems
Ravishankar Krishnaswamy
Jan 27, 2010
ABSTRACT: The group Steiner problem is a classical network design problem where we are given a graph and a collection of groups of vertices, and want to build a min-cost subgraph that connects the root vertex to at least one vertex from each group. What if we wanted to build a subgraph that two-edge-connects the root to each group -- that is, for every group g, the subgraph should contain two edge-disjoint paths from the root to some vertex in g?

In this talk, we describe a technique based on random tree-embeddings that can be used to solve this and other 2-edge-connected network design problems, including the two-edge-connected versions of facility location, buy-at-bulk, and the min-cost 2-connected subgraph spanning k vertices. This is joint work with Anupam Gupta and R. Ravi.