Aspects of Network Design

In this dissertation we study two problems from the area of network design. The first part discusses the multicommodity buy-at-bulk network design problem, a problem that occurs naturally in the design of telecommunication and transportation net-works. We are given an underlying graph and associated with each edge of the graph, a cost function that represents the price of routing demand along this edge. We are also given a set of demands between pairs of vertices each of which needs to be satisfied by paying for sufficient capacity along a path connecting the vertices of the pair. In the multicommodity network design problem the objective is to minimize the cost of satisfying all demands. There are often situations where there is an initial fixed cost of utilizing an edge, or there is discounting or economies of scale that give rise to concave cost functions. We have an instance of the buy-at-bulk network design problem when the cost functions along all edges are concave. Unlike the case of linear cost functions, for which polynomial time algorithms exist, the buy-at-bulk network design problem is NP-hard. We give the first non-trivial approx