Locating tree-shaped facilities using the ordered median objective

In this paper we consider the location of a tree-shaped facility S on a tree network, using the ordered median function of the weighted distances to represent the total transportation cost objective. This function unifies and generalizes the most common criteria used in location modeling, e.g., median and center. If there are n demand points at the nodes of the tree T=(V,E), this function is characterized by a sequence of reals, =(₁, . . . ,_n), satisfying ₁₂..._n0. For a given subtree S let X(S)={x₁, . . . ,x_n} be the set of weighted distances of the n demand points from S. The value of the ordered median objective at S is obtained as follows: Sort the n elements in X(S) in nonincreasing order, and then compute the scalar product of the sorted list with the sequence . Two models are discussed. In the tactical model, there is an explicit bound L on the length of the subtree, and the goal is to select a subtree of size L, which minimizes the above transportation cost function. In the strategic model the length of the subtree is variable, and the objective is to minimize the sum of the transportation cost and the length of the subtree. We consider both discrete and continuous versions of the tactical and the strategic models. We note that the discrete tactical problem is NP-hard, and we solve the continuous tactical problem in polynomial time using a Linear Programming (LP) approach. We also prove submodularity properties for the strategic problem. These properties allow us to solve the discrete strategic version in strongly polynomial time. Moreover the continuous version is also solved via LP. For the special case of the k-centrum objective we obtain improved algorithmic results using a Dynamic Programming (DP) algorithm and discretization and nestedness results.Acknowledgement We would like to thank Noga Alon for the current version of the proof of Theorem 4.1, which simplifies our original proof significantly. J. Puerto also thanks the Spanish Ministerio de Ciencia y Tecnología through grant number BFM2001-2378 for partially supporting his research.