Approximating Minimum Bounded Degree Spanning Trees to within one of Optimal

Mohit Singh (CMU)

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.

The algorithm generalizes when vertices have distinct upper and lower bounds on vertex degrees and returns a spanning tree of optimal cost which violates the degree bounds by an additive one.

The main technique used is the iterative rounding method introduced by Jain in the design of approximation algorithms. Our major technical contribution is to extend the ideas of this method and apply them effectively to a new domain of problems. An unique feature of our iterative rounding algorithm is that it does not round.

The talk will be self-contained.

This is joint work with Lap Chi Lau.

Host: Nick Harvey

(The Algorithms and Complexity Seminar series talks are usually held Thursdays from 4-5:15pm in 32-G575.)