Premium
The continuous and discrete path‐variance problems on trees
Author(s) -
Puerto Justo,
Ricca Federica,
Scozzari Andrea
Publication year - 2009
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20284
Subject(s) - mathematics , vertex (graph theory) , path (computing) , combinatorics , tree (set theory) , variance (accounting) , upper and lower bounds , function (biology) , path length , shortest path problem , longest path problem , mathematical optimization , discrete mathematics , graph , computer science , mathematical analysis , computer network , accounting , evolutionary biology , business , biology , programming language
In this article we consider the problem of locating path‐shaped 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. NETWORKS, 2009