2-medians in trees with pos/neg weights (Q1582068): Difference between revisions

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.