CSAIL Event Calendar: Previous Series

Minimum Bounded Degree Spanning Trees

Speaker: Michel Goemans , MIT
Date: October 3 2006
Time: 4:15PM to 5:30PM
Location: 32-144
Host: Madhu Sudan, MIT

The minimum spanning tree is one the most fundamental combinatorial optimization problems, and its efficient solution makes it of wide applicability in a variety of areas, including network design, routing, communication and clustering. In this talk, I will consider the variant under the additional restriction that all degrees of the spanning tree must be at most a given value $k$. The main result I will describe is that one can efficiently find a spanning tree of maximum degree at most $k+2$ whose cost is at most the cost of the optimum spanning tree of maximum degree $k$. This is almost best possible, as the problem of just deciding whether a graph has a spanning tree of maximum degree $k$ is NP-complete.

The approach uses a sequence of simple algebraic, polyhedral and combinatorial arguments. It illustrates many techniques and ideas in combinatorial optimization as it involves polyhedral characterizations, uncrossing, matroid intersection, and graph orientations (or packing of spanning trees). Little prior knowledge will be assumed; just a willingness to learn...

The result generalizes to the setting where every vertex has upper and lower bounds on its degree. It also gives a better understanding for relaxations of related problems, including the symmetric and asymmetric traveling salesman problems.

See other events that are part of Theory Colloquium Fall 2006

See other events happening in October 2006