The Ordered Median Euclidean Straight-line Location Problem
Antonio J. Lozano, Frank Plastria · 2009
An optimal line is sought in the Euclidean plane in terms of the ordered median criterion, when the set of existing facilities are points with arbitrary positive associated weights. By way of geometric duality a dominating set for such a line is found. This allows the construction of an algorithm to solve the problem in O(n 4 ).