On the Integrality Gap of the Directed-Component Relaxation for Steiner Tree

Abstract

In this note, we show that the integrality gap of the $k$-Directed-Component- Relaxation($k$-DCR) LP for the Steiner tree problem, introduced by Byrka, Grandoni, Rothvob and Sanita (STOC 2010), is at most $\ln (4)<1.39$. The proof is constructive: we can efficiently find a Steiner tree whose cost is at most $\ln (4)$ times the cost of the optimal fractional $k$-restricted Steiner tree given by the $k$-DCR LP.

arXiv commentThis paper has been withdrawn due to a crucial error in Lemma 4. In Lemma 4, additional property for $\{Y_j^{\prime }\}$ is needed to guarantee that the family of distributions exists. However, we can not guarantee the condition for every iteration