A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs

Zachary Friggstad, Jochen Koenemann, Mohammad Shadravan

We demonstrate that the integrality gap of the natural cut-based LP relaxation for the directed Steiner tree problem is $O(\log k)$ in quasi-bipartite graphs with $k$ terminals. Su…