A polynomial time approximation scheme for optimal product-requirement communication spanning trees

Given an undirected graph with nonnegative edge lengths and nonnegative ver tex weights, the routing requirement of a pair of vertices is assumed to be the product of their weights. The routing cost for a pair of vertices on a given spanning tree is defined as the length of the path between them mult iplied by their routing requirement. The optimal product-requirement commun ication spanning tree is the spanning tree with minimum total routing cost summed over all pairs of vertices. This problem arises in network design an d computational biology. Far the special case that all vertex weights are i dentical, it has been shown that the problem is NP-hard and that there is a polynomial time approximation scheme far it. in this paper we show that th e generalized problem also admits a polynomial rime approximation scheme. ( C) 2000 Academic Press.