CSAIL Event Calendar: Previous Series
Approximating Minimum Bounded Degree Spanning Trees to within one of Optimal
Speaker: Mohit Singh , CMU
Relevant URL: http://theory.csail.mit.edu/~madhu/algcomp/mohit-abs.html
In the Minimum Bounded Degree Spanning Tree problem, we are given an edge-weighted undirected graph with degree bound k for each vertex v and the task is to find a spanning tree of minimum cost which satisfies all the degree bounds. In this talk I will present an efficent algorithm which returns a spanning tree in which degree of any vertex v is at most k+1 and whose cost is at most the cost of the optimal spanning tree of maximum degree k. This settles a conjecture of Goemans affirmatively and generalizes a result of Furer and Raghavachari to weighted graphs. This is essentially best possible.