2-medians in trees with pos/neg weights
Consider the positive/negative 2-median problem on a tree of \(n\) vertices. The authors give an \(O(n^2)\) algorithm to solve the problem when the objective function is given as the sum of the minima of the weighted distances between vertices of the tree and facilities, and an \(O(n^3)\) algorithm to solve the problem when the objective function is given as the sum of the weighted minima of the distances between vertices of the tree and facilities.
scientific article; zbMATH DE number 1512445
scientific article