Quasi-polynomial Time Approximation Algorithm for Low-Degree Minimum-Cost Steiner Trees

摘要

In a recent paper [5], we addressed the problem of finding a minimum-cost spanning tree T for a given undirected graph G=(V,E) with maximum node-degree at most a given parameter Bu3e1. We developed an algorithm based on Lagrangean relaxation that uses a repeated application of Kruskalrsquos MST algorithm interleaved with a combinatorial update of approximate Lagrangean node-multipliers maintained by the algorithm. In this paper, we show how to extend this algorithm to the case of Steiner trees where we use a primal-dual approximation algorithm due to Agrawal, Klein, and Ravi [1] in place of Kruskalrsquos minimum-cost spanning tree algorithm. The algorithm computes a Steiner tree of maximum degree and total cost that is within a constant factor of that of a minimum-cost Steiner tree whose maximum degree is bounded by B. However, the running time is quasi-polynomial.