A linear time algorithm for computing minmax regret 1-median on a tree network (Q486974)

The facility location problem is to minimize the communication or transportation costs. The cost function is formulated as the sum of distances from the nearest facility weighted by the weights of the vertices. The previous most efficient algorithm for finding minimum regret 1-median in a tree network with nonnegative vertex weights takes \(O(n\log n)\) time. The author's algorithm takes linear time, i.e. \(O(n)\).