Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
Jochen Könemann, R. Ravi · SIAM Journal on Computing · 2005
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 \in V$, the output tree has degree at most O(B v + log|V|) for every $v \in V$. As before, the cost of the tree is at most a constant times that of a minimum-cost tree obeying all degree bounds.