The continuous and discrete path variance problem on trees

The Continuous and Discrete Path Variance Problem on Trees Justo Puerto1, Federica Ricca2, Andrea Scozzari2 1Universidad de Sevilla Dep. Estad´ıstica e Investigaci´on Operativa [email protected] ∗ 2Universit`a di Roma “La Sapienza” Dip. Statistica, Probabilit`a e Statistiche Applicate {federica.ricca, andrea.scozzari}@uniroma1.it † 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 nvertices, 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 [5]. Finally, we show that no nestedness property holds for (discrete and continuous) point-variance problem with respect to the corresponding path-variance. Keywords: Path location, variance criterion, equity measures. 1 Introduction Network facility location consists of locating facilities in a network in order to supply a set of costumers. During the last two decades there has been increasing attention to extensive facilities location models, that is, the location of connected structures such as path-shaped or tree-shaped facilities [6, 17, 19]. For a comprehensive review see for example [9, 18]. In these models the objective function is given either by the sum of the distances from each client to its nearest facility (median criterion), or by the maximum of these distances (center criterion). However, some authors have considered the problem of finding an optimal location of a path or a tree using either the two criteria simultaneously or a convex combination of them [1, 3, 14, 15, 16]. ∗The research of this author is partially supported by Spanish research grants number: MTM2004:0909. †The research of these authors is partially supported by the Italian research grants “Azioni Integrate Italia- Spagna” (number 2.1.4.4.1.15). 1 Problem 1Continuous Discrete Point Variance O(n) [7] O(n) [10] Path Variance2O(n2)O(n2) Path Variance with Bounded Length O(n2)O(n2) Table 1: Summary of results. In recent years some authors started to study location problems with equity measures as objective function. The idea is that some salient features of real problems, like the dispersion of the clients’ demand with respect to a facility, are not captured by the traditional objective functions. The dispersion measures are strictly related to the variability of the distribution of the distance from demand points to a facility and they seem to be particularly relevant when locating facilities in the public sector applications, such as the location of evacuation routes or the location of a highway in a road network. A part of the literature devoted to location problems with equity measures is concerned with providing efficient algorithms for different objective functions. A review of the existing literature about equity measures in location theory can be found in [8]. Actually, almost all the papers focusing on equity measures deal with the location of a single point on a network [7, 10]. However, some papers related to the location of extensive facilities with equity measure appeared in the recent years: [5] provides a polynomial algorithm for locating a continuous path of minimum variance on tree networks, that is, the problem of locating a continuous path by minimizing the variance of the distance travelled by the customers to a facility. In addition, in [13] a path problem is studied with respect to the range objective function, which is given by the difference between the maximum and the minimum distance from a facility and to the Hurwicz objective function, which is given by a convex combination of the maximum and the minimum distance from the points of the network to the facility. Finally, [4] studies the problem of locating a path in a tree minimizing the coefficient of variation function, that is, the ratio between the squared root of the variance and the average distance. In this paper we study the problem of locating a path-shaped facility on a tree minimizing the variance objective function. 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 consider 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 on some vertex of the tree. Given a tree with nvertices, 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 nterm the previous algorithm presented in [5] (see Table 1). Moreover, we show that our algorithms can be applied also for the location of a path with other equity measures related to the variance function, such as the coefficient of variation. Furthermore, with respect to the point and the vertex location problem with minimum variance, we show that the nestedness property does not hold. In fact, we provide two coun- 1Boldfaced results are new results in the paper. 2Nestedness property with respect to the point variance does not hold in any case. 2 terexamples showing that the continuous path that minimizes the variance function on a tree does not necessarily contain the point of minimum variance, and the discrete path that minimizes the variance function on a tree does not necessarily contain the vertex of minimum variance. The paper is organized as follows. In Section 2 we introduce the continuous path-variance problem with unrestricted length and provide a polynomial O(n2) time algorithm for solving it. The same is done in Section 3 for the discrete version of this problem, while Section 4 is devoted to the path-variance problems with bounded length. Finally, in Section 5 we draw some conclusions and provide extensions of our results. 2 The Continuous Path-Variance Problem We are given a tree T= (V, E) with |V|=n. To each vertex vis associated a positive weight w(v), while to each edge e= (v, u) is assigned a positive real length `vu. We may assume that W(T) = Pv∈Vw(v) = 1 and interpret each w(v) as the fraction of the population that lives in vertex v[7]. Given any two points xand yin Tthat may be vertices or may belong to the interior of an edge, we denote by d(x, y) the length of the unique path Pxy from xto y. Given a path Pxy, the sum of the weighted distances from all the vertices of Tto Pxy is: D(Pxy) = X v∈V w(v)d(v, Pxy) where d(v, Pxy) is the distance from a vertex vto the path Pxy. Denote by V AR(Pxy) the variance of a path Pxy which is defined: V AR(Pxy) = X v∈V w(v)(d(v, Pxy)−D(Pxy))2. By referring to the well-known variance decomposition formula [7] we can re-write V AR(Pxy) as follows V AR(Pxy) = X v∈V w(v)d(v, Pxy)2−D(Pxy)2. If we denote by Q(Pxy) = Pv∈Vw(v)d(v, Pxy)2the sum of the weighted squared distances, the above formula becomes: V AR(Pxy) = Q(Pxy)−D(Pxy)2. The Continuous Path-Variance Problem consists of finding the path Px∗y∗between two points x∗and y∗in Tsuch that V AR(Px∗y∗)≤V AR(Pxy), ∀x, y ∈T. Similarly, the corresponding Continuous Point-Variance Problem on Tcan be formulated as the problem of finding the point x∗in Tsuch that V AR(x∗)≤V AR(x), ∀x∈T. The following result shows that the point in T of minimum variance is not necessarily contained in Px∗y∗. Remark 1. Given a tree T, a point x∈Tthat minimizes the variance objective function is not necessarily contained in a path of minimum variance. Let us consider the tree in Figure 1. This is the same tree depicted in [7] but with the weight 3 assigned to the edge (4,3) equal to 10 in place of 4. We assign weights equal to 1 8to each vertex. By applying the linear time algorithm presented in [7], the point x∗of minimum variance in Tis located on the edge (4,3) at a distance d(x∗,3) = 8.214. The value of the objective function at x∗is V AR(x∗) = 14.214. The path that minimizes the variance among all the paths containing the point x∗is the one whose end points are located at a distance equal to 2 to vertex 5 and equal to 2 to vertex 3, and such that its variance is equal to 11.750. The path that minimizes the variance in Tis the path P15 with V AR(P15) = 10.937 This path does not contain the edge (4,3) and, consequently, it does not contain the point x∗of minimum variance.       1 2 4 8 6 5 7 4 6 32 3 5 8.214 1.786 3 x* Figure 1: An example of a tree where the path of minimum variance does not contain the minimum variance point. In our algorithm, for each edge we compute all the paths in Tthat minimize the variance and having a starting point in the given edge. In order to do this, consider an edge (r, s), and let Trand Tsbe the two subtrees obtained by removing (r, s) from T. First suppose to root T at vertex sand let T(s) = Tr∪Ts∪(r, s) be the resulting rooted tree. By visiting top down level-by-level the subtree Tr⊂T(s), for each edge (v, u)∈Trwe find the path Pxy that minimizes the variance function with x∈(r, s) and y∈(v, u). Then, we consider ras the new root of Tand, by visiting Ts⊂T(r) top down, for each edge (v, u)∈Tswe find the path Pxy that minimizes V AR(Pxy) with x∈(r, s) and y∈(v, u). Suppose we are given a path P¯x¯ywhere ¯xbelongs to the edge (r, s) and ¯yto the edge (v, u)∈Tr(see Figure 2). In a rooted tree we may always assume that vis closer to the root sthan uin T(s). For convenience, we denote by x∈(r, s) (y∈(v, u)) both the point along the edge and the distance of the point from r(from v). Given a path P¯x¯ywe have to compute the squared sum of the weighted distances D(Pxy)2of a new path Pxy =P¯yy ∪P¯x¯y∪P¯xx with x∈(r, s) and ybelonging to an edge (u, m)∈Tu⊆Tradjacent to the edge (v, u). D(Pxy)2can be computed as follows: D(Pxy)2= [D(P¯x¯y)−Sav(P¯yy)−Sav(P¯xx)]2 where Sav(P¯yy) and Sav(P¯xx) are the reductions (savings) in the sum of the weighted distances D(P¯x¯y) obtained by attaching to the path P¯x¯ythe two paths P¯yy and P¯xx, respectively [11, 12]. In a rooted tree Tr, we denote by W(Tv) = Pk∈Tvw(k) the sum of the weights of the vertices kbelonging to a subtree Tv⊆Trand by D(P¯x¯y;Tv) the sum of the distances of all the vertices k∈Tv⊆Trfrom the path P¯x¯y. We have: Sav(P¯yy) = d(¯y, u)W(Tu\Tm) + d(¯y, y)W(Tm). Since by definition d(¯y, y) = d(¯y, u) + y, and W(Tu\Tm) + W(Tm) = W(Tu), Sav(P¯yy) becomes: 4 v s T y rs x \Tm Tu m u Tm Figure 2: Basic elements in the construction of Pxy when visiting Tr⊂T(s). Sav(P¯yy) = d(¯y, u)W(Tu) + yW (Tm).(1) Similarly, to compute Sav(P¯xx) we have: Sav(P¯xx) = (x−¯x)W(Ts).(2) We note that Sav(P¯xx) may be positive or negative depending on the position on the edge (r, s) of the new point xwith respect to the old point ¯x. Hence, the squared sum of the weighted distances D(Pxy)2of the path Pxy can be expressed as a quadratic function of the two (unknown) points yand xas follows: D(Pxy)2= [D(P¯x¯y)−d(¯y, u)W(Tu)−yW (Tm)−(x−¯x)W(Ts)]2.(3) Note that in (3) D(P¯x¯y)−d(¯y, u)W(Tu) is constant. Moreover, D(P¯x¯y) is the current value of the sum of the distances of the path P¯x¯y, while d(¯y, u) = `vu −¯y. The value W(Tv) can be computed for all the vertices v∈T(s) in linear time by visiting bottom up level-by-level the rooted tree T(s) in a preprocessing phase [2]. Let us now consider the savings in the sum of the weighted squared distances Q(P¯x¯y) when we consider the new path Pxy =P¯yy ∪P¯x¯y∪P¯xx with ybelonging to an edge (u, m)∈Tu adjacent to (v, u), and xbelonging to (r, s). As before, only the vertices in the two subtrees Tu⊆Trand Tsare involved in the computation of the savings. In particular, let us consider the saving obtained when the path P¯yy is added to P¯x¯y. By considering the vertices in Tuwe have: QSav(P¯yy) = X k∈Tu\Tm w(k)[d(k, ¯y)2−d(k, u)2] + X k∈Tm w(k)[d(k, ¯y)2−d(k, y)2]. 5 Since d(k, ¯y) = d(k, u) + d(u, ¯y) for all the vertices k∈Tu\Tm, and d(k, ¯y) = d(k, y) + d(¯y, y) for all the vertices k∈Tm, by substituting in the above formula we obtain: QSav(P¯yy) = d(u, ¯y)2W(Tu\Tm) + 2d(u, ¯y)D(u;Tu\Tm) +(d(u, ¯y) + y)2W(Tm) + 2(d(u, ¯y) + y)D(y;Tm) (4) with D(y;Tm) = D(m;Tm) + (`um −y)W(Tm). Let us now consider the saving in the sum of the weighted squared distances of the path P¯xx. In this case only the vertices in the subtree Tsare involved in the computation. Then we have QSav(P¯xx) = X k∈Ts w(k)[d(k, ¯x)2−d(k, x)2]. Since for all the vertices k∈Tswe have d(k, ¯x) = d(k, x) + (x−¯x), and Pk∈Tsw(k)d(k, ¯x) = D(¯x;Ts), we have: QSav(P¯xx) = (x−¯x)2W(Ts) + 2(x−¯x)D(x;Ts).(5) with D(x;Ts) = D(s;Ts) + (`rs −x)W(Ts). Even in this case QSav(P¯xx) can be positive or negative according to the position of the point ¯xwith respect to x. The sum of the weighted squared distances of the new path Pxy as a function of the two variables xand yis: Q(Pxy) = Q(P¯x¯y)−d(u, ¯y)2W(Tu\Tm)−2d(u, ¯y)D(u;Tu\Tm) −(d(u, ¯y) + y)2W(Tm)−2(d(u, ¯y) + y)D(y;Tm) −(x−¯x)2W(Ts)−2(x−¯x)D(x;Ts). (6) From (3) and (6) follows that the variance of the path Pxy can be written as a function φ(x, y) of the two variables xand y: V AR(Pxy) = φ(x, y) = Q(Pxy)−D(Pxy)2.(7) As proved in [5], the variance is a strictly convex function on the compact set [0,`rs]×[0,`um]. Thus, the two points y∈(u, m) and x∈(r, s) can be computed by solving the following system of linear equations:      ∂φ(x,y) ∂x = 0 ∂φ(x,y) ∂y = 0 (8) Note that when the points xand/or ydo not belong to the above compact set, they belong to 6 the boundary of the set [0,`rs]×[0,`um]. Hence, similar cases described in [5] must be considered and, in particular, we have:        x=`rs if x≥`rs x= 0 if x≤0 y=`um if y≥`um y= 0 if y≤0 (9) For a given pair of edges (r, s) and (v, u) we define a best path P¯x¯y(v, u) the path of minimum variance among all the paths Pxy with x∈(r, s) and y∈(v, u). Given an edge (r, s), with the previous formulas we are able to compute the best path P¯x¯y(v, u) for each possible edge (v, u) of a given rooted tree. In order to solve the Continuous Path-Variance problem on a tree T, we must also consider the case in which the optimal path lies within a single edge, including the special case when the optimal path is a point. For this case we can simply refer to the procedure provided in [5]. In the following we sketch a pseudo-code of the algorithm for solving the Continuous Path- Variance problem on a tree T. —————————————————————————————— CONTINUOUS PATH-VARIANCE Input: A weighted tree T. Output: A continuous path P∗of minimum variance V AR(P∗) in T. 1. Solve the path-variance problem for each edge eof T(see [5]) and let P(e) be the best path on eand V ar(P(e)) the corresponding variance 2. for each edge e= (a, b)∈T 3. Let P∗ e=P¯x¯y(a, b) = P(e), with ¯x, ¯y∈e 4. repeat steps 5-13 for r=aand s=band for r=band s=a 5. root the tree Tat vertex sand let T(s) be the resulting rooted tree 6. visit T(s) bottom up and compute all the information at all the vertices v∈V 7. visit top down level-by-level the subtree rooted at rand let Trbe the rooted tree 8. for each edge (u, m)∈Tr 9. find x∈(r, s) and y∈(u, m) by solving (8) and V AR(Pxy) by using (7) 10. let P¯x¯y(u, m) = Pxy 11. if V AR(P¯x¯y(u, m)) < V AR(P∗ e)then 12. P∗ e=P¯x¯y(u, m) 13. V AR(P∗ e) = V AR(P¯x¯y(u, m)) 14. Let P∗= argmine{V AR(P∗ e)} 15. output P∗and V AR(P∗) —————————————————————————————— Lemma 1. The CONTINUOUS PATH-VARIANCE algorithm finds the path P∗of minimum variance in T. Proof. It is clear that an optimal path exists in T. Indeed, it is either included in a single edge or its end points are contained in two different edges of T. In the first case, the optimal 7 path is found at step 1 of the above algorithm by the procedure given in [5]. In the second case, we can compute the variance of a path Pxy,x∈(r, s) and y∈(u, m), through formula (7) where the function φ(x, y) is updated by the saving functions Sav(·) and QSav(·). In both these savings the quantities that are function of xare independent from those that are function of y. Thus, given a path P¯x¯y, for x∈(r, s) and y∈(u, m), V ar(Pxy) can be correctly updated from V ar(P¯x¯y) by computing Sav(·) and QSav(·) with respect to the vertices in the two subtrees Tu⊆Trand Ts, separately. Since the variance function is strictly convex on the compact set [0,`rs]×[0,`um] (see [5]), a path that minimizes φ(x, y) among all the paths Pxy with x∈(r, s) and y∈(u, m) can be correctly found by solving (8). Since our algorithm computes the best path P¯x¯yfor all the possible pairs of edges of a given tree T, it correctly finds a path P∗of minimum variance in T.¤ Lemma 2. The CONTINUOUS PATH-VARIANCE algorithm finds the path P∗of minimum variance in O(n2) time. Proof. Given a tree T(s) rooted at a vertex s, and for each subtree Tu⊆T(s), all the quantities we use in our algorithm, that is, W(Tu), D(u;Tu), D(u;Tu)2can be computed once in O(n) time in a preprocessing phase. The path-variance problem restricted to an edge can be solved in linear time for all the edges in T. Starting from a path P¯x¯y, the saving formulas Sav(·) and QSav(·) can be computed in constant time. The system given by (8) is linear in the two variables xand yand then it is solvable in constant time. Since the algorithm must be repeated for all the possible edges (r, s)∈T, the overall time complexity is O(n2). ¤ 3 The Discrete Path-Variance Problem In this section we consider the Discrete Path-Variance Problem on a tree. Let T= (V, E) be a tree with |V|=n. As before, we assume that a positive weight w(v) is associated to each vertex v∈Vand a positive real length `vu is assigned to each edge (v, u)∈E. Here we adopt the same notation as before and consider the same assumptions over the weights w(v), v∈V. The Discrete Path-Variance Problem on a tree Tconsists of finding the path Pv∗u∗ between two vertices v∗and u∗in Vsuch that V AR(Pv∗u∗)≤V AR(Pvu), ∀v, u ∈V. Similarly, the corresponding Discrete Vertex-Variance Problem on Tcan be formulated as the problem of finding the vertex v∗∈Vsuch that V AR(v∗)≤V AR(v), ∀v∈V. In the following, if there is no possibility of confusion we omit the end points of a path and we simply write Pin place of Pvu. In order to solve the Discrete Path-Variance Problem, we provide an O(n2) algorithm based on quantities similar to those used in Section 2. Recall that, given a path P, the sum of the weighted distances from all the vertices of Tto Pis denoted by D(P) = X v∈V w(v)d(v, P ) where d(v, P ) is the distance from a vertex vto its closest vertex lying in the path P. According to this, the variance of a path Pis given by V AR(P) = X v∈V w(v)(d(v, P )−D(P))2 8 and can always be decomposed into the difference between the weighted sum of the square distances and the square of the sum of the weighted distances as follows: V AR(P) = X v∈V w(v)d(v, P )2−D(P)2=Q(P)−D(P)2. Remark 2. Given a tree T, a vertex v∈Tthat minimizes the variance objective function is not necessarily contained in a discrete path of minimum variance. Let us consider the tree Tin Figure 3. This is the same tree of Figure 1 but with an additional vertex (numbered by 9). Suppose that we associate to the vertices 1-8 a weight equal to 1 (8+²)and to the vertex 9 a weight equal to ² (8+²),² > 0. If we choose ²= 0.1 the vertex that minimizes the variance is the new vertex 9 with value V AR(9) = 14.861. The path that minimizes the variance among all the discrete paths that contain vertex 9 is P35, with value V AR(P35) = 12.888, but the path that minimizes the variance in Tis P15 with value V AR(P15) = 10.806. 1 2 8 6 5 7 4 6 32 3 5 4 1.786 9 3 8.214 Figure 3: An example of a tree where the discrete path of minimum variance does not contain the vertex of minimum variance. Remark 3 A discrete path Pin Tthat minimizes V AR(P) does not necessarily have its end vertices in the leaves of T. Consider the tree in Figure 4 with 9 vertices, with all edge lengths equal to 1 and all the weights of the vertices equal to 1 9. The path Pfrom vertex 1 to vertex 3 is the one that minimizes the variance objective function. In our algorithm, given a vertex r, we root the tree at rand compute the variance of all the paths in Thaving a starting point in r. Then, by rooting Tat each vertex v∈Vwe are able to find a path Pv∗u∗of minimum variance among all paths Pvu,v, u ∈V. Suppose that the tree Tis rooted at a vertex r∈V, and let Trbe the resulting rooted tree. Let Tvbe a subtree of Trrooted at vertex v. Given a path Pstarting from rto a vertex v, the squared sum of the weighted distances of a path P0=P∪(v, u), where ubelongs to the set S(v) of the children of vin Tvcan be computed as follows: 9 [13] J. Puerto, F. Ricca, A. Scozzari (2005). Extensive Facility Location Problems on Networks with Equity Measures, Technical Report del Dipartimanto di Matematica per le Decisioni Economiche, Finanziarie ed Assicurative, anno XII, n. 4. [14] J. Puerto, A.M. Rodr´ıguez-Ch´ıa, A. Tamir, D. P´erez. The Bi-Criteria Doubly Weighted Center-Median Path Problem On A Tree, Networks, to appear. [15] J. Puerto, A. Tamir (2005). Locating Tree-shaped Facilities Using the Ordered Median Objective, Mathematical Programming A, 102, 313-338. [16] A. Tamir, J. Puerto, D. P´erez-Brito (2002). The Centdian Subtree on Tree Networks, Discrete Applied Mathematics, 118, 263-278. [17] A. Shioura, M. Shigeno (1997). The Tree Center Problems and the Relationship with the Bottleneck Knapsack Problems, Networks, 29, 107-110. [18] A. Tamir, J. Puerto, J. A. Mesa, A. M. Rodr´ıguez-Ch´ıa (2005). Conditional Location of Path and Tree Shaped Facilites on Trees, Journal of Algorithms, 56, 50-75. [19] A. Tamir (1998). Fully Polynomial Approximation Schemes for Locating a Tree-shaped Facility: a Generalization of the Knapsack Problem, Discrete Applied Mathematics, 87, 229-243. 16