Improved Algorithms for the Minmax-Regret 1-Center and 1-Median Problems
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).
general graphs trees location theory minmax-regret optimization centers medians