Minmax regret median location on a network under uncertainty

We consider the 1-median problem on a network with uncertain weights of nodes. Specifically, for each node, only an interval estimate of its weight is known. It is required to find the ‘mini-max regret’ location, i.e., to minimize the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. We present the first polynomial algorithm for this problem on a general network. For the problem on a tree network, we discuss an algorithm with an order of complexity improved over the algorithms known in the literature.