Polylogarithmic Approximation for
Minimum Communication Spanning Trees
David Peleg ?
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. firstname.lastname@example.org. Supported in part by a grant from the Israel Science Foundation and by a grant from the Israel Ministry of Science and Art.