Polylogarithmic Approximation for

Minimum Communication Spanning Trees

David Peleg ?

Abstract

This paper considers a problem introduced in [Hu74], concerning the selection of a minimum communication spanning tree (MCT) for a given weighted network, namely, a tree that minimizes the total cost of transmitting a given set of communication requirements between n sites over the tree edges. Some special cases of the problem are solved in [Hu74].

An equivalent but slightly different formulation of the problem is given in [AKPW95], based on the concept of a spanning tree of low average stretch for weighted connected multigraphs. An algorithm is presented in [AKPW95] for constructing a spanning tree with average stretch O(2
plogn) for any given multigraph, yielding an approximation
algorithm for the MCT problem with a similar approximation ratio. It is conjectured in [AKPW95] that the true bound on average stretch is O(log n).

This paper shows that for every weighted complete multigraph (with arbitrary multiplicities) there exists a spanning tree whose average stretch is bounded by O(ln5=2 n ? ln D), where D is the network's diameter. The proof yields an approximation algorithm for minimum communication spanning trees with ratio O(ln5=2 n ? ln D).

?Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, 76100 Israel. peleg@wisdom.weizmann.ac.il. Supported in part by a grant from the Israel Science Foundation and by a grant from the Israel Ministry of Science and Art.