Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks

In a model of facility location problem, uncertain vertex weights are represented by intervals of possible weights, and one looks for a “robust” solution that minimizes the maximum “regret” (Kouvelis et al., 1993). We first give an O(n)O(n) time algorithm for the path networks, and then present an O(nlogn)O(nlogn) time algorithm for the tree networks, which improves upon the previously best algorithm for this problem (Yu et al., 2008) with time complexity O(nlog2n)O(nlog2n). We also present an O(nlogn)O(nlogn) time algorithm for the unicycle networks, which contain just one cycle. Our cactus algorithm runs in O(nlog2n)O(nlog2n) time. There is no previously published result tailored specifically for cactus networks. In solving these problems, we introduce a number of data structures, which we believe are useful for other applications.