Name: Michel Goemans
University: MIT
Date: Friday, April 28, 2006
Time: 1:30 to 3:00 pm
Location: Simon Auditorium, Posner Hall
Title of Seminar: Abstract of Bounded-Degree Minimum Spanning Trees
Abstract
In this lecture, we consider a basic problem in network design, namely the minimum cost spanning tree problem with the restriction that all degrees must be at most a given value $k$. This is an NP-hard problem. We show that we 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. 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. The result generalizes to the setting where every vertex has both upper and lower bounds. Other extensions will also be discussed.
