The complexity of the capacitated tree problem
Christos H. Papadimitriou · Networks · 1978
Abstract We examine the complexity of a classical problem related to the design of centralized computer networks. Under very broad assumptions the problem is shown to be NP‐complete, and hence most probably intractable. The same result holds for the “Euclidean” case of the problem; however, in the latter case a simple algorithm produces solutions with relative error almost certainly arbitrarily close to zero.