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.