Approximating minimum-cost degree-bounded spanning trees without solving linear programs

In the minimum-cost degree-bounded spanning tree problem, we are given
an undirected graph with nonegative costs on the edges and a
degree-upper-bound parameter B. The goal is to find a minimum-cost
spanning tree among those of maximum node-degree B.

We show how to compute a spanning tree of maximum degree O(B+log(n))
and cost O(opt) where opt is the minimum cost of any degree-B-bounded
spanning tree, and n is the number of nodes of the graph. While
similar guarantees were dervied in our previous work, it relied on
solving a linear program. In this talk, we will describe a direct
procedure that builds upon the primal-dual method.


This is joint work with R. Ravi.