Minmax-regret robust 1-median location on a tree

This paper considers the minmax-regret 1-median problem on a tree network where edge lengths and node weights are uncertain and the uncertainty is characterized by given intervals. Some localization properties for the optimal locations, for both the node-restricted and the unrestricted cases, are derived. Using these properties, efficient algorithms are developed for finding the minmax-regret 1-median locations for both cases. An example is provided to illustrate the algorithm.