Additive Guarantees for Degree Bounded Directed Network Design

The problem of finding a minimum spanning tree that satisfies given degree bounds on vertices has received much attention in the field of combinatorial optimization recently. This problem was first studied by Furer and Raghavachari. Their motivation was to find a broadcast tree in a communication network along which the maximum overload of any node, proportional to its degree, is minimized. Assuming unit edge-costs, they gave a local-search based polynomial-time algorithm for computing a spanning tree with maxi-mum degree at most ?+1 as long as there exists a spanning tree with maximum degree at most ?. This is essentially the best possible since computing the optimum is NP-hard.