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.