Dual Growth with Variable Rates: An Improved Integrality Gap for Steiner Tree

A promising approach for obtaining improved approximation algorithms for Steiner tree is to use the bidirected cut relaxation (BCR). The integrality gap of this relaxation is at least $36/31$, and it has long been conjectured that its true value is very close to this lower bound. However, the best upper bound for general graphs is still $2$. With the aim of circumventing the asymmetric nature of BCR, Chakrabarty, Devanur and Vazirani [Math. Program., 130 (2011), pp. 1--32] introduced the simplex-embedding LP, which is equivalent to it. Using this, they gave a $\sqrt{2}$-approximation algorithm for quasi-bipartite graphs and showed that the integrality gap of the relaxation is at most $4/3$ for this class of graphs. In this paper, we extend the approach provided by these authors and show that the integrality gap of BCR is at most $7/6$ on quasi-bipartite graphs via a fast combinatorial algorithm. In doing so, we introduce a general technique, in particular a potentially widely applicable extension of the primal-dual schema. Roughly speaking, we apply the schema twice with variable rates of growth for the duals in the second phase, where the rates depend on the degrees of the duals computed in the first phase. This technique breaks the disadvantage of increasing dual variables in a monotone manner and creates a larger total dual value, thus presumably attaining the true integrality gap.