A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree Network
In a model of facility location problem, the uncertainty in the weight of a vertex is represented by an interval of weights, and the objective is to minimize the maximum regret. The most efficient algorithm previously known for finding the minmax regret 1-median in a tree network with nonnegative vertex weights takes O(nlogn) time. We improve it to O(n), settling the open problem posed by Brodal et al. (Oper. Res. Lett. 36:1418, 2008).
minmax regret facility location robust median uncertain weights