Computer Science/Discrete Mathematics Seminar I

Buy-at-bulk network design problems arise in telecommunication networks and related fields where economies of scale result in concave cost functions for purchasing bandwidth. A basic problem in this area is the following. We are given a graph G=(V,E) which represents an underlying network. We are also given a demand matrix in the form of pairs s_1t_1, s_2t_2, ..., s_kt_k with each pair s_it_i requesting a bandwidth of d_i units. The goal is to satisfy these bandwidth requests at minimum cost by buying capacity on the links of the network. The cost of buying a capacity on link e is given by a concave cost function f_e; that is f_e(x) is the cost of buying capacity of x units on link e. In this talk we present a new algorithm for this problem that yields an O(log^4 k) approximation ratio. This is the first poly-logarithmic approximation when the functions f_e can be different for different links. The algorithmic idea is intuitive and is amenable to various heuristic implementations. The analysis illustrates a simple but effective high level scheme that allows one to reduce a multi-commodity problem to essentially a single-commodity problem. Time permitting, some recent uses of this scheme will be mentioned. Joint work with M.T. Hajiaghayi, G. Kortsarz and M.R. Salavatipour