A Min-Max Theorem for <i>p</i>-Center Problems on a Tree

Abstract

This paper considers the problem of locating p facilities on a tree network in order to minimize the maximum distance from a point on the network to its nearest facility. Such a problem might arise, for example, in optimally locating a fixed number of fire hydrants along a street network. The present, paper identifies an underlying min-max theorem that governs such a p-center problem. More specifically, this p-center problem is shown to be equivalent to the “dual” problem of locating p + 1 points on the network so as to maximize the minimum distance between pairs of points.