






















In the Directed Steiner Tree (DST) problem, we are given a directed graph $G=(V,E)$ on $n$ vertices with edge-costs $c \in \mathbb{R}_{\geq 0}^E$, a root vertex $r \in V$, and a set $K \subseteq V \setminus \{r\}$ of $k$ terminals. The goal is to find a minimum-cost subgraph of $G$ that contains a path from $r$ to every terminal $t \in K$. DST has been a notorious problem for decades as there is a large gap between the best-known polynomial-time approximation ratio of $O(k^ε)$ for any constant $ε> 0$, and the best quasi-polynomial-time approximation ratio of $O\left(\frac{\log^2 k}{\log \log k}\right)$. Towards understanding this gap, we study the integrality gap of the standard flow LP relaxation for the problem. We show that the LP has an integrality gap of $Ω(n^{0.0418})$. Previously, the integrality gap of the LP is only known to be $Ω\left(\frac{\log^2n}{\log\log n}\right)$ [Halperin~et~al., SODA'03 \& SIAM J.~Comput.] and $Ω(\sqrt{k})$ [Zosin-Khuller, SODA'02] in some instance with $\sqrt{k}=O\left(\frac{\log n}{\log \log n}\right)$. Our result gives the first known lower bound on the integrality gap of this standard LP that is polynomial in $n$, the number of vertices. Consequently, we rule out the possibility of developing a poly-logarithmic approximation algorithm for the problem based on the flow LP relaxation.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。