Consider the unweighted p-center problem with rectilinear distances. Suppose there are m demand points. Since m can be quite large, we may need to aggregate the demand points into a collection of q points Z, with p ≪ q < m. The result is an approximating p-center problem. This aggregation causes error for each p-center, X, say e(X:Z). There is a well-defined error bound function, say b(Z), satisfying e(X:Z) ≤ b(Z) for all X. Ideally one would choose Z to minimize b(Z), a q-center function, but this is an NP-Hard problem. We obtain instead an overestimate of b(Z), say b+(Z), and provide a lower bound on the minimal value b+(Z). We give necessary and sufficient conditions for this lower bound to be attained, and a constructive aggregation algorithm to attain the lower bound asymptotically as q increases. Thus, we obtain an aggregation procedure which (1) allows controlling the maximum error by adjusting q, and (2) gives a basis of comparison for heuristics that minimize b(Z).
