Primal-Dual Meets Local Search: Approximating MSTs With Nonunifor.pdf.pdf' (227.53 kB)

Download file# 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 ∈ V, the output tree has degree at most O(B_{v}+ log|V|) for every v ∈V. As before, the cost of the tree is at most a constant times that of a minimum-cost tree obeying all degree bounds.