TY - GEN

T1 - Tree embeddings for two-edge-connected network design

AU - Gupta, Anupam

AU - Krishnaswamy, Ravishankar

AU - Ravi, R.

PY - 2010

Y1 - 2010

N2 - 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 ⊆ V, the subgraph should contain two edge-disjoint paths from the root to some vertex in g? What if we wanted the two edge-disjoint paths to end up at distinct vertices in the group, so that the loss of a single member of the group would not destroy connectivity? In this paper, we investigate tree-embedding techniques that can be used to solve these and other 2-edge-connected network design problems. We illustrate the potential of these techniques by giving poly-logarithmic approximation algorithms for two-edge-connected versions of the group Steiner, connected facility location, buy-at-bulk, and the k-MST problems.

AB - 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 ⊆ V, the subgraph should contain two edge-disjoint paths from the root to some vertex in g? What if we wanted the two edge-disjoint paths to end up at distinct vertices in the group, so that the loss of a single member of the group would not destroy connectivity? In this paper, we investigate tree-embedding techniques that can be used to solve these and other 2-edge-connected network design problems. We illustrate the potential of these techniques by giving poly-logarithmic approximation algorithms for two-edge-connected versions of the group Steiner, connected facility location, buy-at-bulk, and the k-MST problems.

UR - http://www.scopus.com/inward/record.url?scp=77951670727&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951670727&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973075.124

DO - 10.1137/1.9781611973075.124

M3 - Conference contribution

AN - SCOPUS:77951670727

SN - 9780898717013

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1521

EP - 1538

BT - Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Association for Computing Machinery (ACM)

T2 - 21st Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 17 January 2010 through 19 January 2010

ER -