Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

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 networks. 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 approximation algorithm for the general case of

the problem with arbitrary concave costs along the edges. Our algorithm is

conceptually very simple and has an approximation guarantee of

$e^{O(\sqrt{\log n \log \log n}\,)}\log D$, where $n$ is the number of

demand pairs and $D$ is the maximum demand.The second part of the thesis examines the *Terminal Backup* problem that

arises when facilities storing data would like to be connected to at least

one other facility for data backup purposes. In the *Terminal

Backup*problem we are given a graph with terminal nodes, non-terminal

nodes and

edge costs. The objective is to find the cheapest forest connecting every

terminal to at least one other terminal. We show that this problem is

reducible to *Simplex Matching*, a variant of 3D matching that we introduce.In an instance of *Simplex Matching*, we are given a hypergraph with edges

of size at most three and edge costs associated with them. We show how to

find the minimum cost perfect matching of this hypergraph efficiently if the

edge costs obey a simple and realistic inequality we call the *Simplex

Condition*.While motivated by the desire of solving the *Terminal Backup* problem, the

usefulness of the *Simplex Matching* algorithm we develop is not limited to

*Terminal Backup*. We briefly discuss additional problems where *Simplex

Matching* can be successfully employed.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/92

[2] ftp://ftp.cs.princeton.edu/techreports/2007/803.pdf