Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem Original Research Article

Given an n-node tree T = (V,E), we are concerned with the problem of selecting a subtree of a given length which optimizes the sum of weighted distances of the nodes from the selected subtree. This problem is NP-hard for both the minimization and the maximization versions since it generalizes the knapsack problem. We present fully polynomial approximation schemes which generate a (1 + ε)-approximation and a (1 − ε)-approximation for the minimization and maximization versions respectively, in O(n2g3) time.