The continuous and discrete path variance problem on trees

Abstract

In this paper we consider the problem of locating path-shaped facilities on a tree minimizing the variance objective function. This kind of objective function is generally adopted in location problems which arise in the public sector applications, such as the location of evacuation routes or mass transit routes. We consider the general case in which a positive weight is assigned to each vertex of the tree and positive real lengths are associated to the edges. We study both the 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 the case in which the path is discrete, that is, the end points of the optimal path must lie in some vertex of the tree. Given a tree with n vertices, for both these problems we provide algorithms with O(n2) time complexity and we extend our results also to the case in which the length of the path is bounded above. Even in this case we provide polynomial algorithms with the same O(n2) complexity. In particular, our algorithm for the continuous path-variance problem improves upon a log n term the previous best known algorithm for this problem provided in [T. Cáceres, M.C. López-de-los-Mozos, J.A. Mesa (2004). The path-variance problem on tree networks, Discrete Applied Mathematics, 145, 72-79]. Finally, we show that no nestedness property holds for (discrete and continuous) point-variance problem with respect to the corresponding path-variance.