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

摘要

In a recent paper, 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 B > 1. We developed an algorithm based on Lagrangean relaxation that uses a repeated application of Kruskal's 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 in place of Kruskal's minimum-cost spanning tree algorithm. The algorithm computes a Steiner tree of maximum degree O(B + log n) 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.