The continuous and discrete path-variance problems on trees

In this article we consider the problem of locating pathshaped facilities on a tree network, minimizing the variance objective function. This type of objective is generally adopted in location problems arising in public sector applications, such as the location of evacuation or mass transit routes. We consider a weighted tree, in which a positive weight is assigned to each vertex of the tree, and positive real lengths are associated with its edges. We study the general case in which the path is continuous, that is, the end points of the optimal path can be either vertices, or points along an edge, and there is an upper bound on the length of the path. Given a tree with n vertices, for this problem we provide an O(n 2) algorithm, and we show how it can be applied, with the same complexity, to the discrete case, that is, when the end points of the optimal path are vertices of the tree. We improve the previous best complexity bound in (Cáceres et al., Discr Appl Math 145 (2004), 72-79), for the unrestricted length continuous path-variance problem, by a factor of log n. We also show that the optimal point for the variance objective function does not satisfy any nestedness property with respect to the optimal path in the unconstrained (discrete or continuous) version of the problem. © 2008 Wiley Periodicals, Inc.