Approximating Survivable Network Design via Rounding-by-Tree-Embedding

difficult problems on general graphs into amenable tree instances. A
notable application of "metric-tree" embedding is in the design of
approximation algorithm for the group Steiner tree problem (GST).
While the metric-tree embedding has numerous applications, it has a
limitation that it is not applicable for survivable network design, in
which we require 2 or more edge-disjoint paths, because we would lose
connectivity information in the process of obtaining a
metric-completion graph. In this talk, we explore applications of the
cut-base tree-embedding in the design of approximation algorithms for
survivable network design, namely, the k-edge-connected group Steiner
tree problem (k-GST). We then generalize our techniques to problems
directed graphs in which tree-embedding in usual sense does not exist
and present approximation algorithms for the k-edge-connected directed
Steiner tree problem (k-DST).

This talk is based on a joint work with Parinya Chalermsook and
Fabrizio Grandoni and a following up work.