| Title | Approximation Algorithms for Buy-at-Bulk Network Design Problems |
| Speaker | Prof. MohammadReza Salavatipour, University of Alberta |
| Web page | http://www.cs.ualberta.ca/~mreza/ |
| Time | Tuesday, May 2, 3:00pm |
| Location | SSL 150 |
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 Ω(log^{1/4-ε} n) for any ε > 0. We give the first poly-logarithmic approximation algorithm for this problem.
Joint work with: Chandra Chekuri, MohammadTaghi Hajiaghayi, and Guy Kortsarz.