Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Approximating Survivable Network Design via Rounding-by-Tree-Embedding
Speaker:Bundit Laekhanukit
coming from:Weizmann Institute of Science
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 30 June 2016
Duration:30 Minutes
Building:E1 4
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 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.

Name(s):Parinya Chalermsook
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created:Parinya Chalermsook, 06/16/2016 03:38 PM Last modified:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Parinya Chalermsook, 06/27/2016 09:28 PM
  • Parinya Chalermsook, 06/16/2016 03:38 PM -- Created document.