Optimal routing trees for the AT&T advanced-800 service.

The AT&T advanced-800 service provides a subscriber with control over incoming calls from its customers. The incoming calls are directed to various destinations according to a d-dimensional matrix provided by the subscriber where each dimension represents a certain feature. The actual routing is done by a switching system which processes the features of a call sequentially and thus can be modeled as a decision tree. A cost L sub i is charged for each link associated with the feature i. The problem is to construct a routing tree with minimum link cost. Recently, this problem has been shown to be NP-complete.