Quasi-polynomial Time Approximation Algorithm for Low-Degree Mini.pdf.pdf' (216.33 kB)

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

journal contribution

posted on 2010-07-01, 00:00 authored by Jochen Könemann, Ramamoorthi RaviRamamoorthi RaviIn 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 B>1. 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.