Optimal Locations on a Line Are Interleaved

Suppose n facilities are to be located on a fine segment so as to minimize cost function. One might expect that the facilities' optimal locations have the following interleaving property: if one of the n facilities is removed and if the locations of the others are shifted by reoptimizing, each remaining facility's location shifts toward the location of the one removed, but not farther toward it than the original location of the adjacent facility. This paper presents two models whose solutions have this interleaving property and four examples of such models. An additive criterion is used in one model, a minimax criterion in the other. In the additive model, the minimum cost is a convex function of n; in the minimax model, it is nonincreasing.