O(log2 k/loglogk)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm (Shi Li)


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 subgraph that contains a directed path from r to every terminal. We present an O(log2 k/loglogk)-approximation algorithm for DST that runs in quasi-polynomial-time. By making standard assumptions, and 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].
Based on joint work with Fabrizio Grandoni and Bundit Laekhanukit.


2019-07-22   14:00 ~ 15:00   


Shi Li, University at Buffalo


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