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.