Tech Report CS-93-41

Steiner Trees and Beyond: Approximation Algorithms for Network Design

Ramamurthy Ravi

September 1993

Abstract:

We present approximation algorithms for several NP-hard optimization problems arising in network design. Almost all of our algorithms run in polynomial time and output solutions with a worst-case performance guarantee on the quality of the output solution.

A typical problem that we consider can be stated as follows: given an undirected graph and certain connectivity requirements, find a subgraph that satisfies these requirements and has minimum cost. In this thesis, we address many different connectivity requirements such as spanning trees, Steiner trees, generalized Steiner forests, and two-connected networks. The cost criteria that we consider range from the total cost of the edges in the network, the total cost of the nodes in the network, the maximum degree of any node in the network, the maximum cost of any edge in the network to some combination of these. We also address the maximum-leaf spanning tree problem and provide the first approximation algorithms for this problem.

In the course of deriving our results, we use three distinct techniques: the primal-dual technique that draws on the theory of linear programming, local optimization, and a solution-based decomposition method. Our work highlights the applicability of these techniques to designing approximation algorithms.

(complete text in pdf or gzipped postscript)