A minmax regret median problem on a tree under uncertain locations of the demand points

This paper deals with the location of a new facility on a tree according to the minimization of the weighted distance to the customers. The weights represent demands of the set of nodes. The exact location of each customer will be assumed unknown but close   to its corresponding node. In this context, an algorithm to find a minmax regret median is proposed and its complexity is shown to be O(nlog(n))$O(nlog\left(n\right))$, where n$n$ is the number of nodes of the tree