Premium
The complexity of the capacitated tree problem
Author(s) -
Papadimitriou C. H.
Publication year - 1978
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230080306
Subject(s) - simple (philosophy) , euclidean geometry , mathematical optimization , tree (set theory) , mathematics , computer science , computational complexity theory , combinatorics , algorithm , philosophy , geometry , epistemology
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.