Title:  Degree bounded network design


Speaker:  Nikhil Bansal, IBM-Watson


 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.