SPEAKER: MohammadTaghi Hajiaghayi TIME: Wednesday 12-1pm, November 1, 2006 PLACE: NSH 1507 TITLE: Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design and Related Problems ABSTRACT: We consider approximation algorithms for non-uniform buy-at-bulk network design problems. Buy-at-bulk network design problems arise in settings where economies of scale and/or the availability of capacity in discrete units result in concave or sub-additive cost functions on the edges. One of the main application areas is in the design of telecommunication networks. The typical scenario is that capacity (or bandwidth) on a link can be purchased in some discrete units u_1 < u_2 < ... < u_r with costs c_1 < c_2 < ... < c_r such that the cost per bandwidth decreases c_1/u_1 > c_2/u_2 > ... > c_r/u_r. The capacity units are sometimes referred to as cables or pipes. A basic problem that needs to be solved in this setting is the following: given a set of bandwidth demands, install sufficient capacity on the links of an underlying network topology so as to be able to route the demands. The goal is to minimize the total cost. Alternatively, we can think of the following scenario. We have two independent cost functions on the links of the network: a buy cost b(e) a rent cost r(e). We are given a set of demands between some pairs of nodes. A feasible solution for the non-uniform multicommodity buy-at-bulk instance is to buy some links and rent some other ones such that all the demands can be routed and the total cost is minimized; the cost of every bought edge is b (e) and for rented edges it is r(e) per unit of flow (bandwidth) over that link. This problem generalizes several classical problems, such as minimum cost flow to the settings that the cost of each edge is a concave monotone function. It is known that the problem is hard to approximate within a factor of \Omega(log^{1/4-\eps} n) for any \eps>0. We give the first poly- logarithmic approximation algorithm for this problem. Time permitting we will mention the applications of our approach for stochastic two-stage network design and network design with vertex costs.