Aspects of Network Design (thesis)

Abstract:

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.