Approximating Survivable Network Design via Rounding-by-Tree-Embedding (Bundit Laekhanukit)

Abstract

Tree-Embedding is a powerful technique for graph problems that reduces 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 and introduce a problem specific tree embedding for the k-edge-connected directed Steiner tree problem (k-DST) and the classical group Steiner tree problem (GST). As a result, we obtain the first non-trivial approximation algorithms for a special case of k-DST and a general case of 2-DST. We further obtain an O(log^2 n)-approximation algorithm for GST on bounded treewidth graphs, which improves upon the previous best approximation ratio of O(log^3 n) by Garg et al., [SODA’98 & J. Algorithms 00].
This talk is based on joint works with Parinya Chalermsook, Syamantak Das, Fabrizio Grandoni and Daniel Vaz.

Time

2017-02-22   14:00 ~ 15:00   

Speaker

Bundit Laekhanukit,The Weizmann Institute of Science

Room

Room 308,School of Information Management & Engineering, Shanghai University of Finance & Economics