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.