Abstract

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-costarborescence that contains a directed path from r to every terminal. We presentan O(log^2 k/log log{k})-approximation algorithm for DST that runs inquasi-polynomial-time. By adjusting the parameters in the hardness result ofHalperin and Krauthgamer [STOC’03], we show the matching lower bound ofOmega(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 classicalquasi-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 twomain ingredients.

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

This is a joint work withFabrizio Grandoni and Shi Li.

Time

12月27日（周四）15:00-16:00

Speaker

Bundit Laekhanukit iscurrently an Associate Professor in the Institute for Theoretical ComputerScience at the Shanghai University of Finance and Economics. He is originallyfrom Thailand. He completed his Ph.D. from the McGill University in 2014 underthe supervision of Adrian Vetta. After the completion of his Ph.D., he had beenat the Swiss AI Lab IDSIA as a postdoctoral researcher under the supervision ofFabrizio Grandoni. He joined the Simons Institute for the Theory of Computingas a research fellow twice in Fall 2014 and Fall 2017 under Simons-ICORE andSimons-MPI joint fellowship programs. He spent two years at the WeizmannInstitute for Science under the Simons-ICORE joint fellowship program, hostedby Uriel Feige and Robert Krauthgamer, and he spent two semesters at theMax-Planck-Institut für Informatik under the Simons-MPI joint fellowshipprogram, hosted by Kurt Mehlhorn before officially joining SUFE.

Hisresearch interests lie in the intersection between approximation algorithms,the hardness of approximations, parameterized complexity, and fine-grainedcomplexity. Shortly, he is interested in (but not limited to) understanding theinteraction between the running time of algorithms and the approximationguarantees ones can achieve with perhaps dependency on some parameters of aninput.

Venue

信息管理与工程学院602室

上海财经大学（第三教学楼西侧）

上海市杨浦区武东路100号