Minmax Regret 1-Center on a Path/Cycle/Tree

Abstract—In a facility location problem in computational geometry, if the vertex weights are uncertain one may look for a “robust ” solution that minimizes “regret. ” The best previously known algorithm for finding the minmax regret 1-center in a tree with positive vertex weights is due to Yu et al., and runs in sub-quadratic asymptotic time in the number of vertices. Assuming that the minimum weight of at least one vertex is non-negative, we present a new, conceptually simpler algorithm for a tree with the same time complexity, as well as an algorithm that runs in linear (respectively sub-quadratic) time for a path (respectively cycle). Index Terms—facility location; 1-center; minmax regret opti-mization I