Primal-dual meets local search:: Approximating msts with nonuniform degree bounds

We present a new bicriteria approximation algorithm for the degree-bounded minimum-cost spanning tree (MST) problem: Given an undirected graph with nonnegative edge weights and a degree bound B, find a spanning tree of maximum node-degree B and minimum total edge-cost. Our algorithm outputs a tree of maximum degree at most a constant times B and total edge-cost at most a constant times that of a minimum-cost degree-B-bounded spanning tree. While our new algorithm is based on ideas from Lagrangian relaxation, as is our previous work [SIAM J. Comput., 31 ( 2002), pp. 1783 - 1793], it does not rely on computing a solution to a linear program. Instead, it uses a repeated application of Kruskal's MST algorithm interleaved with a combinatorial update of approximate Lagrangian node-multipliers maintained by the algorithm. These updates cause subsequent repetitions of the spanning tree algorithm to run for longer and longer times, leading to overall progress and a proof of the performance guarantee. A second useful feature of our algorithm is that it can handle nonuniform degree bounds on the nodes: Given distinct bounds B-v for every node v is an element of V, the output tree has degree at most O(B-v + log |V |) for every v is an element of V. As before, the cost of the tree is at most a constant times that of a minimum-cost tree obeying all degree bounds.