We give the first constant-factor approximation algorithm for quasi-bipartite instances of Directed Steiner Tree on graphs that exclude fixed minors. In particular, for $K_r$-minor-free graphs our approximation guarantee is $O(r\cdot\sqrt{\log r})$ and, further, for planar graphs our approximation guarantee is 20. Our algorithm uses the primal-dual scheme. We employ a more involved method of determining when to buy an edge while raising dual variables since, as we show, the natural primal-dual scheme fails to raise enough dual value to pay for the purchased solution. As a consequence, we also demonstrate integrality gap upper bounds on the standard cut-based linear programming relaxation for the Directed Steiner Tree instances we consider.
翻译:我们给出了第一个常量要素近似值算法,用于准两边的指向型施泰纳树(指向型树),其图表不包括固定未成年人。特别是,对于无固定未成年人的平面图,我们的近似保证是$O(r\rdot\sqrt\sqrt\log r}),对于平面图,我们的近似保证是20。我们的算法使用原始双向计划。我们采用了一种更复杂的方法来决定何时购买边缘,同时提高双重变量,因为正如我们所显示的那样,自然的原始双向计划无法筹集足够的双倍价值来支付购买的解决方案。因此,我们还展示了我们所考虑的“直接施泰纳树”事件标准削减线性规划松动的一体化差距。