New geometry-inspired relaxations and algorithms for the metric Steiner tree problem (Q647390)

The main focus of this paper is the bidirected cut relaxation for the metric Steiner tree problem. It is known that this problem is NP-complete. Hence, for practical applications, approximation algorithms are necessary. The best approximation algorithm for the Steiner problem is due to Robins and Zelikovsky. The authors prove a guarantee of \({1.55}\) for general graphs and also show that when restricted to the quasi-bipartite graphs, i.e., graphs that do not have edges connecting pair of Steiner nodes, the ratio is \(1.28\). However, it is not clear whether these results would imply an upper bound on the integrality gap of the bidirected cut relaxation. The authors of this paper restrict themselves to quasi-bipartite graphs. We note that the class of quasi-bipartite graphs is a non-trivial class for the bidirected cut relaxation. The best known upper bound on the integrality gap on such graphs was \(3/2\) (Rajagopalan and Vazirani). In Section 4 of this paper the authors describe the dual growing procedure (the EMBED algorithm) which helps to prove the following property about the bidirected cut relaxation in quasi-bipartite graphs: if the minimum spanning tree is the optimum Steiner tree, than the LP relaxation is exact. In Section 5 the authors show how to modify the EMBED algorithm and give a primal-dual algorithm achieving the upper bound of \(3/2\). This algorithm can be made to run in almost linear time. We note that Rizzi's algorithm runs in time \((O(n^{2}T(n,m)\log_{2}{c_{m}}))\) where \(T(n,m)\) is the time taken to compute the minimum spanning tree in an \(n\) nodes, \(m\) edges graph, while \(c_m\) is the maximum cost of an edge. Using a way of reducing costs, the authors describe in Section 6 a simple and fast algorithm which proves an upper bound of \(\sqrt{2}\) on the integrality gap for quasi-bipartite graphs. This algorithm runs in strongly polynomial time. In Section 7, using another way of reducing costs, the authors present a \(4/2\) factor approximation algorithm, which takes the same time as Rizzi's algorithm. We believe that the geometric approach of the authors would open up new ways to use the primal-dual schema for the bidirected cut relaxation.