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(n log n) time. We improve it to O(n), settling the open problem posed by Brodal et al. (Oper. Res. Lett. 36:14-18, 2008).