New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem

Determining the integrality gap of the bidirected cut relaxation for the metric Steiner tree problem, and exploiting it algorithmically, is a long-standing open problem. We use geometry to define an LP whose dual is equivalent to this relaxation. This opens up the possibility of using the primal-dual schema in a geometric setting for designing an algorithm for this problem. Using this approach, we obtain a 4=3 factor algorithm and integrality gap bound for the case of quasi-bipartite graphs; the previous best integrality gap upper bound being 3/2 [RV99]. We also obtain a factor p 2 strongly polynomial algorithm for this class of graphs. A key difficulty experienced by researchers in working with the bidirected cut relaxation was that any reasonable dual growth procedure produces extremely unwieldy dual solutions. A new algorithmic idea helps finesse this difficulty { that of reducing the cost of certain edges and constructing the dual in this altered instance { and this idea can be extracted into a new technique for running the primal-dual schema in the setting of approximation algorithms.