Approximating minimum bounded degree spanning trees to within one of optimal

Abstract

In the Minimum Bounded Degree Spanning Tree problem, we aregiven an undirected graph with a degree upper bound Bv on eachvertex v, and the task is to find a spanning tree of minimumcost which satisfies all the degree bounds. Let OPT be the costof an optimal solution to this problem. In this paper, we presenta polynomial time algorithm which returns a spanning tree T ofcost at most OPT and dT(v) ≤ Bv+1 for all v, where dT(v) denotes the degree of v in T. This generalizes aresult of Furer and Raghavachari [8] to weighted graphs, andsettles a 15-year-old conjecture of Goemans [10] affirmatively. The algorithm generalizes when each vertex v hasa degree lower bound Av and a degree upper bound Bv, andreturns a spanning tree with cost at most OPT and Av - 1 ≤dT(v) ≤ Bv + 1 for all v. This is essentially the bestpossible. The main technique used is an extension of the iterativerounding method introduced by Jain [12] for the design ofapproximation algorithms.