Minmax regret median location on a network under uncertainty

We consider the I-median problem on a network with uncertain weights of nod es. Specifically, for each node, only an interval estimate of its weight is known. It is required to find the "minimax regret" location, i.e., to mini mize 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 netwo rk. For the problem on a tree network, we discuss an algorithm with an orde r of complexity improved over the algorithms known in the literature.