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.

The continuous and discrete path-variance problems on trees / Justo, Puerto; Ricca, Federica; Andrea, Scozzari. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 53:2(2009), pp. 221-228. [10.1002/net.20284]

The continuous and discrete path-variance problems on trees

RICCA, Federica;
2009

Abstract

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.
2009
variance criterion; equity measures; path location
01 Pubblicazione su rivista::01a Articolo in rivista
The continuous and discrete path-variance problems on trees / Justo, Puerto; Ricca, Federica; Andrea, Scozzari. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 53:2(2009), pp. 221-228. [10.1002/net.20284]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/366046
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 10
social impact