摘要
When there is no constraint on the length, efficient algorithms are known for the minmax regret path center, path median, and path centdian problems on trees. In a recent review on location problems, these problems with length constraint were considered as open. The focus of this paper is the minmax regret path center problem with length constraint on a tree. Efficient algorithms are presented for both the continuous and discrete models, which require, respectively, O(nlg 2 n) and O(nlgn) time. Our algorithms are based on an approach introduced by Averbakh and Berman for solving the minmax regret p-center problem. To apply their approach, we give a sufficient condition under which the approach works. This result is of independent interest. According to the condition, polynomial algorithms are obtained immediately for the minmax regret versions of many other center location problems, for which no algorithms were known before.