CSAIL Event Calendar: Previous Series

Approximating Minimum Bounded Degree Spanning Trees to within one of Optimal

Speaker: Mohit Singh , CMU
Date: March 8 2007
Time: 4:00PM to 5:15PM
Location: 32-G575
Host: Nick Harvey, MIT CSAIL

Contact: Joanne Hanley, 617 253 6054, joanne@csail.mit.edu
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.

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.

See other events that are part of Algorithms and Complexity Series 2006/2007

See other events happening in March 2007