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 “minimax 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 p roblem on a tree network, we discuss an algorithm with an order of complexity improved over the algorithms known in the literature.