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:An O(log^2{k}/log log {k})-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
Speaker:Bundit Laekhanukit
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 4 July 2019
Duration:30 Minutes
Building:E1 4
In the Directed Steiner Tree (DST) problem we are given an n-vertex directed edge-weighted graph, a root r, and a collection of k terminal

nodes. Our goal is to find a minimum-cost arborescence that contains a directed path from r to every terminal. We present an O(log^2 k/log log{k})-approximation algorithm for DST that runs in quasi-polynomial-time. By adjusting the parameters in the hardness result of Halperin and Krauthgamer [STOC'03], we show the matching lower bound of Omega(log^2{k}/log log{k}) for the class of quasi-polynomial-time algorithms. This is the first improvement on the DST problem since the classical quasi-polynomial-time O(log^3 k) approximation algorithm by Charikar et al. [SODA'98; J. Algorithms'99] (The paper erroneously claims an O(log^2k) approximation due to a mistake in prior work.) Our approach is based on two main ingredients.

First, we derive an approximation preserving reduction to the Label-Consistent Subtree (LCST) problem. The LCST instance has quasi-polynomial size and logarithmic height. We remark that, in contrast, Zelikovsky's heigh-reduction theorem used in all prior work on DST achieves a reduction to a tree instance of the related Group Steiner Tree (GST) problem of similar height, however losing a logarithmic factor in the approximation ratio. Our second ingredient is an LP-rounding algorithm to approximately solve LCST instances, which is inspired by the framework developed by Rothvoss [Preprint, 2011]. We consider a Sherali-Adams lifting of a proper LP relaxation of LCST. Our rounding algorithm proceeds level by level from the root to the leaves, rounding and conditioning each time on a proper subset of label variables. A small enough (namely, polylogarithmic) number of Sherali-Adams lifting levels is sufficient to condition up to the leaves.

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

Created:Antonios Antoniadis, 03/21/2019 05:09 PM Last modified:Uwe Brahm/MPII/DE, 03/26/2019 04:01 AM
  • Antonios Antoniadis, 03/21/2019 05:09 PM
  • Antonios Antoniadis, 03/21/2019 05:09 PM -- Created document.