Title: Buy-at-bulk Network Design and Variants

In the buy-at-bulk network design problem, we are given traffic
requirements for various commodities in a network. The flow of these
commodities must be routed along the edges of the network by installing
cables; The cables are available in different types that allow lower
per-unit routing cost for higher installation price. The task is to
choose and install cables on the edges of the network to route all the
traffic at minimum total cable cost.

In the first part of this talk, Ravi will discuss the salient principles
underlying the various approaches to designing approximation algorithms
for the single-sink version of the above problem. In the second part,
Amitabh describes in more detail a variant incorporating elements of
facility location into this model. He will present a constant
factor approximation algorithm for the single-cable version of this
problem.