Abstract
In this article, efficient algorithms are presented for the minmax-regret 1-center and 1-median problems on a general graph and a tree with uncertain vertex weights. For the minmax-regret 1-center problem on a general graph, we improve the previous upper bound from O(mn 2 log n) to O(mn log n). For the problem on a tree, we improve the upper bound from O(n 2 ) to O(n log 2 n). For the minmax-regret 1-median problem on a general graph, we improve the upper bound from O(mn 2 log n) to O(mn 2 + n 3 log n). For the problem on a tree, we improve the upper bound from O(n log 2 n) to O(n log n). © 2008 ACM.