ABSTRACT
Computing the minimum cost spanning tree in an undirected graph is well understood since the 1920's. However, consider the generalization where we are given degree bounds b_v on each vertex v, and we want to find the minimum cost spanning tree subject to these bounds. In a recent break through result, Goemans gave a LP based approximation algorithm that computes the minimum cost tree, while violating the degree bounds by at most an additive +2. This was subsequently improved and simplified by Singh and Lau who gave an additive guarantee of +1.
In this talk, I will describe a new extremely simple proof of the +1 result. Then I will discuss extensions to directed graphs, matroids and more general network design problems. Most of the talk will consist of giving a flavor of the polyhedral techniques used in the design and analysis of these algorithms.
Joint work with Rohit Khandekar and Viswanath Nagarajan.
Back to Seminar Series schedule page
