The traditional multi-commodity flow problem assumes a given flow netw
ork in which multiple commodities are to be maximally routed in respon
se to given demands. This paper considers the multi-commodity flow net
work-design problem: given a set of multi-commodity flow demands, find
a network subject to certain constraints such that the commodities ca
n be maximally routed. This paper focuses on the case when the network
is required to be a tree. The main result is an approximation algorit
hm for the case when the tree is required to be of constant degree. Th
e algorithm reduces the problem to the minimum-weight balanced-separat
or problem; the performance guarantee of the algorithm is within a fac
tor of 4 of the performance guarantee of the balanced-separator proced
ure. If Leighton and Rao's balanced-separator procedure is used, the p
erformance guarantee is O(log n). This improves the O(log(2)n) approxi
mation factor obtained by a direct application of the balanced-separat
or method.