Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal

In the MINIMUM BOUNDED DEGREE SPANNING TREE problem, we are given an undirected graph with a degree upper bound Bv on each vertex v, and the task is to find a spanning tree of minimum cost which satisfies all the degree bounds. Let OPT be the cost of an optimal solution to this problem. In this paper, we present a polynomial time algorithm which returns a spanning tree T of cost at most OPT and dT (v) ≤ Bv + 1 for all v, where dT (v) denotes the degree of v in T. This generalizes a result of Furer and Raghavachari [8] to weighted graphs, and settles a 15-year-old conjecture of Goemans [10] affirmatively. The algorithm generalizes when each vertex v has a degree lower bound Av and a degree upper bound Bv, and returns a spanning tree with cost at most OPT and Av − 1 ≤ dT (v) ≤ Bv + 1 for all v. This is essentially the best possible. The main technique used is an extension of the iterative rounding method introduced by Jain [12] for the design of approximation algorithms.