Tech Report CS-91-60

Network Design and Network Cut Dualities: Approximation Algorithms and Applications

Ajit Kumar Agrawal

September 1991

Abstract:

We give approximation algorithms for two network design problems. These problems arise in designing communication networks where a prespecified set of sites needs to be connected through a network. Different applications judge the merit of the networks using different cost criteria. We consider two such cost criteria. Under the first criterion, a network of minimum total edge-cost is to be designed. This problem is known as the {\em Steiner-tree problem.} Under the second criterion, the network's maximum degree is to be minimized; this is referred to as the {\em min-degree problem.} Both these problems are known to be NP-complete.

Our algorithms output a network in polynomial time whose cost is within a small multiplicative factor of the minimum network cost. Our algorithm for the Steiner-tree problem extends to a more general setting of the connectivity requirements of the network known as the {\em generalized Steiner problem.} No approximation algorithms were previously known for either the generalized Steiner problem or the min-degree problem.

Underlying the proofs of performance for the above algorithms are approximate min-max equality relations, which we establish, between the network design problems and some combinatorial problems in finding network cuts. In turn, we also provide approximation algorithms for these combinatorial problems related to network cuts, and describe their applications.

We also apply a previously known approximation algorithm for yet another combinatorial quantity related to network cuts to a problem that arises in the solution of sparse linear systems. We present the first polynomial-time algorithm that finds an elimination ordering that guarantees approximately optimal fill in solving certain symmetric sparse linear systems. Our algorithm is a variant of the well-known nested dissection algorithm and uses a result of Leighton and Rao for finding a balanced node separator in a graph. We also give some experimental results showing the quality of the elimination orderings produced by our algorithm.

(complete text in pdf)