An improved algorithm for the minmax regret median problem on a tree

We consider the 1-median problem with uncertain weights for nodes. Specifically, for each node, only an interval estimate of its weight is known. It is required to find a minmax regret location, that is, to minimize the worst-case loss in the objective function that may occur because the decision is made without knowing which state of nature will take place. For this problem on a tree, the best published algorithm has complexity O(n²). We present an algorithm with complexity O(n log² n).