Primal-dual algorithms come of age: Approximating MST's with nonuniform degree bounds

on minimum-cost degree-bounded spanning trees:
Given an undirected graph with nonnegative edge weights and degree bounds
$B_v>1$ for all vertices $v$, find a spanning tree $T$ of minimum total
edge-cost such that the maximum degree of each node $v$ in $T$ is at most
$B_v$. Our algorithm finds a tree in which the degree of each
node $v$ is $O(B_v+\log n)$ and the total edge-cost is at most
a constant times the cost of any tree that obeys all degree
constraints.

The new algorithm achieves similar guarantees as our previous
result from STOC'00. The new algorithm is direct in the sense
that it does not need to solve an LP to compute the approximate
solution. The algorithm demonstrates the use of a novel hybrid
between primal-dual and local-search algorithms.

We will also outline how the above can be extended to approximate
minimum-cost degree-bounded Steiner trees.

This is joint work with R. Ravi at CMU.