Multifacility ordered median problems on networks: a further analysis

Multifacility Ordered Median Problems on Networks: A Further Analysis Jo¨ rg Kalcsics, Stefan Nickel Fraunhofer Institut fu¨ r Technound Wirtschaftsmathematik, Kaiserslautern, Germany Justo Puerto Universidad de Sevilla, Sevilla, Spain In this paper, we address the ordered p-median problem, which includes as special cases most of the classical multifacility location problems discussed in the literature. Finite dominating sets (FDS) are known for particular instances of this problem: p-median, p-center, and p-centdian. We find an FDS for the ordered p-median problem. This set allows us to gain a better insight into the general FDS structure of network location problems. This FDS is later used to present the first polynomial time algorithm for p-facility ordered median problems on tree networks. This result is combined with some approximation algorithms to give an O(log Mlog log M) approximate solution of these problems on general networks, where Mis the number of vertices. ©2003 Wiley Periodicals, Inc. Keywords: location theory; finite dominating sets; algorithms; complexity 1. INTRODUCTION One of the most important and well-developed branches in location theory are location problems on networks. Numerous surveys and textbooks give evidence of this fact. (See Mirchandani and Francis [13], Labbe´ et al. [12], Drezner [4], Puerto [17], Drezner and Hamacher [5] and references therein.) The starting point of this development may be considered the node-dominance result of Hakimi [7] and the extensions by Hooker et al. [8], which we will show to be essential. In a series of previous papers, a new type of objective function in location theory was introduced and analyzed (see Nickel and Puerto [15], Puerto and Ferna´ndez [18], Rodrı´guez-Chı´a et al. [20], Francis et al. [6], Nickel [14], and Kalcsics et al. [10]). In this paper, we will analyze the p-facility version of this new type of objective function called ordered median function which is a generalization of the most popular objective functions: median, center, centdian, k-centrum, among many others. For networks, this new objective function was first defined in Nickel and Puerto [15] to prove many well-known results in a much easier way and to gain better insight into the geometrical structure of the network with respect to different criteria. In this paper, we discuss the conditions under which finite dominating sets (FDS) for the multifacility formulation of these problems can be derived. Recall that an FDS is a set which always contains an optimal solution of the problem. See Hooker et al. [8] for further details. Identifying a general FDS for this family of problems has important implications on the development of the same kind of efficient algorithms for all these problems simultaneously. Let ᏺ⫽(Ᏻ,l) denote a network with underlying undirected graph Ᏻ⫽(ᐂ,Ᏹ), with node set ᐂ⫽{v 1 ,..., v M } and edge set Ᏹ⫽{e 1 ,..., e N }. For an undirected graph Ᏻ, an edge e僆Ᏹis defined as e⫽[v i ,v j ]⫽[v j , v i ], v i ,v j 僆ᐂ. Associated to each edge e僆Ᏹ, there is a positive length l(e) defined by the function l:Ᏹ3⺢ ⫹ .Byd(v i ,v j ), we denote the length of a shortest path between v i and v j measured by l. Through w:ᐂ3⺢, every vertex is assigned a nonnegative weight. For short, we write w i :⫽ w(v i ) for a node v i 僆ᐂ. A point on an undirected edge e⫽[v i ,v j ] is defined as a pair x⫽(e,t), t僆[0, 1], with d共vk,x兲⫽d共x,vk兲:⫽min兵d共vk,vi兲⫹tl共e兲, d共vk,vj兲⫹共1⫺t兲l共e兲其, for any v k 僆ᐂ. The set of all points of a network ᏺis denoted by ᏼ(Ᏻ). It should be noted that this set also Received October 1, 2000; accepted August 1, 2002 Dedicated to Prof. Dr. Rainer Burkard (Graz) on the occasion of his 60th birthday Correspondence to: J. Puerto Contract grant sponsor: Spanish DGICYT; contract grant number: BFM012378 Published online 00 Month 0000 in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/net.10053 ©2003 Wiley Periodicals, Inc. NETWORKS, Vol. 41(1), 000–000 2003 tapraid5/8u-netwrk/8u-netwrk/8u0103/8u0227-03a deangeln S⫽18 11/18/02 20:49 Art: 1053 Input-ljs(ljs) contains the nodes ᐂ. The sets (e,(t 1 ,t 2 )) :⫽{(e,t) 僆ᏼ(Ᏻ):t僆(t 1 ,t 2 ), t 1 ,t 2 僆[0, 1], t 1 ⬍t 2 } are called open subedges of e僆Ᏹ. Analogously, the sets (e,[t 1 ,t 2 ]) :⫽{(e,t)僆ᏼ(Ᏻ):t僆[t 1 ,t 2 ], t 1 ,t 2 僆[0, 1], t 1 ⱕt 2 } are closed subedges of e僆Ᏹ. Furthermore, (e, (0, 1)) is called the interior of edge e. Let pⱖ2 be an integer. Then, for X p :⫽{x 1 ,...,x p } 債ᏼ(Ᏻ), we define the distance from a node v i 僆ᐂto the set X p as d共vi,Xp兲⫽d共Xp,vi兲:⫽min k⫽1,...,p d共vi,xk兲. A point x⫽(e,t) on an edge e⫽[v i ,v j ]僆Ᏹis called abottleneck point if there exists some node v k with w k ⫽0, such that d共x,vk兲⫽d共x,vi兲⫹d共vi,vk兲⫽d共x,vj兲⫹d共vj,vk兲. Let BN i denote the set of all bottleneck points of a node v i 僆ᐂand let Ꮾᏺ :⫽艛 i⫽1 M BN i be the set of all bottleneck points of the graph. For all v i ,v j 僆ᐂ,v i ⫽v j ,w i w j ⫽0define EQ⬘ ij :⫽兵x僆ᏼ共Ᏻ兲:wid共vi,x兲⫽wjd共vj,x兲其. Let EQ ij be the relative boundary of EQ⬘ ij , that is, the set of endpoints of the closed subedges forming the elements in EQ⬘ ij , and let Ᏹᏽ :⫽艛 i,j,i⫽j EQ ij . The points in Ᏹᏽ are called Equilibrium points of ᏺ. To simplify the presentation, we will denote by EQ ij kl 債EQ ij the equilibrium points of nodes v i ,v j on edge [v k ,v l ], for any i,j僆{1, . . . , M} and k,l:[v k ,v l ]僆Ᏹ. Note that 兩EQ ij kl 兩ⱕ2. In the case that 兩EQ ij kl 兩⫽1, we denote for the sake of simplicity by EQ ij kl also the only element of the set EQ ij kl . For X p 債ᏼ(Ᏻ), we define d共Xp兲:⫽共w1d共v1,Xp兲,...,wMd共vM,Xp兲兲 and dⱕ共Xp兲:⫽共w共1兲d共v共1兲,Xp兲,...,w共M兲d共v共M兲,Xp兲兲, with ⵺being a permutation of the set {1, . . . , M} satisfying w共1兲d共v共1兲,Xp兲ⱕw共2兲d共v共2兲,Xp兲ⱕ···ⱕw共M兲d共v共M兲,Xp兲. To simplify the notation, we will denote the entries w i d(v i ,X p ) and w (i) d(v (i) ,X p ) in the above vectors by d i (X p ) and d (i) (X p ), respectively. The ordered p-median problem on ᏺis defined as OM 共⌳兲 :⫽min Xp傺ᏼ共Ᏻ兲 OM ⌳共Xp兲, with OM ⌳共Xp兲:⫽具⌳,dⱕ共Xp兲典 ⫽ 冘 i⫽1 M ␭ id共i兲共Xp兲 and ⌳⫽共 ␭ 1,..., ␭ M兲僆⺢0⫹ M. (1) This problem is the natural multifacility extension of the ordered median problem considered in Nickel and Puerto [15]. The function OM ⌳ (X p ) is called the ordered p-median function. Note that this function is defined pointwise. In the context of continuous location theory, a similar objective function was introduced in Puerto and Ferna´ndez [18] and later studied in Francis et al. [6], Rodrı´guez-Chı´a et al. [20], and Puerto and Ferna´ndez [19]. The rest of the paper is organized as follows: In the next section, we study the ordered p-median problem with a special structure in the ⌳-modeling weights. Under this assumption, we can identify an FDS for the problem, namely, the set of pseudo-equilibrium points (r-extremes). Section 3 uses the characterization of the FDS to present the first polynomial time algorithm for solving these problems on tree networks. This polynomial time algorithm for trees is combined with the general approximation algorithms of Bartal [1] and Charikar et al. [2] to obtain an O(log Mlog log M) approximate solution for the p-facility ordered median problem in general networks. The paper ends with some conclusions. 2. THE ORDERED p-MEDIAN PROBLEM In Nickel and Puerto [15], it was proved that for ␭ 1 ⱖ...ⱖ ␭ M the node set ᐂconstitutes an FDS for the ordered p-median problem and that for arbitrary ⌳ⱖ0, ᐂ 艛Ᏹᏽ is an FDS for the single-facility ordered median problem. We demonstrate by a simple counterexample that this latter dominance result for the single-facility case does not hold for the p-facility case. Example 1. Consider the tree network of Figure 1. Observe that ᐂ艛Ᏹᏽ is not an FDS for the ordered 2-median FIG. 1. Tree network of Example 1. 2 NETWORKS—2003 F1 tapraid5/8u-netwrk/8u-netwrk/8u0103/8u0227-03a deangeln S⫽18 11/18/02 20:49 Art: 1053 Input-ljs(ljs) problem with ⌳⫽(0.2, 0.2,...,0.2, 1). If we restrict X 2 to be in ᐂ艛Ᏹᏽ,the optimal solution is given by X2⫽ 再 EQ13 12 ⫽ 冉 关v1,v2兴,4 9 冊 ,EQ57 57 ⫽ 冉 关v5,v7兴,1 2 冊冎 , with objective value OM ⌳ (X 2 )⫽82 15 ⫽8.13 ៮.If we drop this restriction,we obtain a better solution,namely, X* 2⫽ 再 x*⫽ 冉 关v1,v2兴,2 3 冊 ,EQ57 57 ⫽ 冉 关v5,v7兴,1 2 冊冎 , with an optimal objective function value of 8.0 (see also Fig. 2). Note that x*is neither an equilibrium point nor a vertex. Despite this negative result, we are able to characterize a polynomial-size FDS for an important class of ordered p-median problems. We note in passing that identifying an FDS is of great importance because it allows one to develop algorithms for these problems even if the solutions are not required to be at vertices. Let 1 ⱕk⬍Mand ⌳ k ⫽(a,..., a,b..., b)僆⺢ 0⫹ M , where a⫽ ␭ 1⫽···⫽ ␭ k⫽ ␭ k⫹1⫽···⫽ ␭ M⫽b. Note that the ⌳vectors corresponding to the center, centdian, or k-centrum problem are of this type. See Nickel and Puerto [15]. For aⱖb, the results in [15] ensure that ᐂis an FDS for the problem. Thus, only the case with a ⬍bhas to be further investigated. Example 1 already points out the two main characteristics of a potential FDS for the case a⬍b. First, one of the solution points belongs to the set ᐂ艛Ᏹᏽ :EQ 57 57 . Second, the other solution point, x*, is related to the one in ᐂ艛Ᏹᏽ, namely, there exist two nodes v 1 and v 5 allocated to x* and EQ 57 57 , respectively, such that d 1 (x*) ⫽d 5 (EQ 57 57 ). In general, we will show in the following that there exists an optimal solution X* p such that ●One or more solution points belong to the set ᐂ艛Ᏹᏽ, i.e. X* p 艚(ᐂ艛Ᏹᏽ)⫽A, and ●For every point in X* p ⶿(ᐂ艛Ᏹᏽ), there exists another solution point in X* p 艚(ᐂ艛Ᏹᏽ) and two nodes allocated to each of the two points such that the weighted distances of these two nodes to their respective solution points are equal. The important point is not just to prove the existence of afinite-size FDS for the problem but to identify it. This dominating set can then be used for developing algorithms to solve the problem while the existence itself is of limited use. For the sake of readability, the following proof of the FDS is split into a sequence of four results. Moreover, we first give an informal description of the main arguments of the proofs: Denote by ᏹ:⫽{1, . . . , M} and let X p ⫽{x 1 ,..., x p }債ᏼ(Ᏻ). We define the following sets: Il:⫽兵i僆ᏹ兩d共Xp,vi兲⫽d共xl,vi兲其⶿艛 j⫽0 l⫺1 Ij,l⫽1,...,p, of the indices of nodes which are allocated to x l ,l ⫽1,...,p, where I 0 :⫽A. Note that ties are resolved by allocating nodes to solution points with smallest indices. The objective function OM ⌳ (X p ) can now be rewritten with respect to I l as OM ⌳共Xp兲⫽ 冘 i⫽1 M ␭ iw共i兲d共Xp,v共i兲兲 ⫽ 冘 i僆I1 ␭ iw共i兲d共x1,v共i兲兲⫹···⫹ 冘 i僆Ip ␭ iw共i兲d共xp,v共i兲兲 ⫽:f1共x1兲⫽:fp共xp兲. For a fixed permutation ⵺and fixed allocations I l , the functions f l ,l僆{1, . . . , p}, are, as a sum of concave functions, also concave in x l . Now, consider the tree network given in Figure 1. Let X 2 FIG. 2. The distance functions along [v 1 ,v 2 ] and [v 5 ,v 7 ] of Example 1. NETWORKS—2003 3 F2 tapraid5/8u-netwrk/8u-netwrk/8u0103/8u0227-03a deangeln S⫽18 11/18/02 20:49 Art: 1053 Input-ljs(ljs) ⫽{x 1 ,x 2 } with x 1 ⫽([v 1 ,v 2 ], 11 12) and x 2 ⫽([v 5 ,v 7 ], 3 8) (see Fig. 2). The vector of ordered distance functions for this set of points is d ⱕ (X 2 )⫽(0.25, 1.25, 1.25, 2.5, 3, 4.5, 5, 5.5). Using ⌳⫽(0.2, 0.2,..., 0.2, 1), we get OM ⌳ (X 2 )⫽9.05. Starting from X 2 , we try to obtain a better solution. From Figure 2, observe that fixing x 2 and moving x 1 on its edge a little to the left or right will neither change the order of the distance functions in the vector d ⱕ (X 2 ) nor the allocation of nodes to the solution points. Hence, the permutation ⵺and the index sets I 1 and I 2 remain the same and OM ⌳ ⵺is concave with respect to x 1 . As a result, we can find a descent direction and obtain a better solution. The formal argument is as follows: Define for t僆⺢: x 1 (t):⫽([v 1 ,v 2 ], 11 12 ⫹t) and X 2 (t):⫽{x 1 (t), x 2 }. Let d i (t):⫽w i d(X 2 (t), v i ), i僆ᏹ. The vector of distance functions with respect to tis d(X 2 (t)) ⫽(d i (t)) i⫽1,...,M ⫽(5.5 ⫹6t, 0.25 ⫺3t, 1.25 ⫺3t, 1.25 ⫺3t, 3, 2.5, 5, 4.5). For t⫽0, we obtain d ⱕ (X 2 (t)) ⫽(0.25 ⫺3t, 1.25 ⫺3t, 1.25 ⫺3t, 2.5, 3, 4.5, 5, 5.5 ⫹6t). Now observe that the order of the distance functions does not change for ⫺1 12 ⱕtⱕ1 12. This means that we can move the point x 1 3x 1 (t) by a small amount on its edge (to the left) without disturbing the permutation. Therefore, we can write the objective function as OM ⌳ (X 2 ):⫽9.05 ⫹4.2t, which is a concave function for t僆[⫺1 12,1 12]. Moreover, any value of t,⫺1 12 ⱕt⬍0, will yield a lower objective value. In the above example, the order of the distance functions did not change at all for t僆[⫺1 12,1 12]. But, obviously, even a change in the ordering of only the first k⫺1 or last k⫹1 vertices is not going to be a problem and we can still argue that the objective function value will not increase. The following lemma addresses the circumstances under which we can move a point while not increasing the objective function value and how far we can move it. Lemma 1. Let ᏺ⫽(Ᏻ,l)be an undirected network with nonnegative node weights,X p ⫽{x 1 ,...,x p }債ᏼ(Ᏻ), x˜ ⫽ (e,t)僆X p ,with e 僆Ᏹand t 僆[0, 1] an arbitrary solution point and ⌳ k ⫽(a,...,a,b,...,b)僆⺢ 0⫹ M .Then,there exists a point x⬘⫽(e,t⬘), t⬘僆[0, 1], such that OM ⌳ (X⬘ p ) ⱕOM ⌳ (X p ), where X⬘ p :⫽X p ⶿{x˜}艛{x⬘}, and either x⬘僆ᐂor d共k兲共X⬘ p兲⫽d共k⫹1兲共X⬘ p兲(2) holds. Proof. Let X p ⫽{x 1 ,...,x p }債ᏼ(Ᏻ) with x l ⫽(e l , s l ), l⫽1,...,p, such that X p does not satisfy one of the relations in (2). W.l.o.g., let x 1 ⫽x˜ 僆ᏼ(Ᏻ). Furthermore, we assume that (i)d (n) (X p )⫽d (n⫹1) (X p ) for all n僆{1, . . . , M⫺1} and zz (ii)/ ?v i 僆ᐂ:w i d(v i ,x 1 )⫽w i d(v i ,x l ), that is, none of the nodes is at the same distance from x 1 as to another solution point x l ⫽x 1 . Define for t:X p (t):⫽{x 1 (t), x 2 ,...,x p }, where x 1 (t) :⫽(e 1 ,s 1 ⫹t). Let T:⫽[tគ,t ៮] be an interval with ⫺s 1 ⱕtគ ⬍0⬍t ៮ⱕ1⫺s 1 , such that (i) and (ii) hold for X p (t) for all t僆T. This interval exists since (i) and (ii) are satisfied for t⫽0 and all distance functions d i ⵺are continuous on an edge. Let v i :⫽v (n) , for some n⫽1,...,M, be allocated to x 1 , that is, d (n) (X p )⫽d i (x 1 ). Then, by the above assumptions on X p and the definition of T, we have d (n) (X p (t)) ⫽d i (x 1 (t)), @t僆T. For all nodes v j allocated to x l 僆X p , x l ⫽x 1 ,d (r) (X p (t)) ⫽d j (x l ), for some r⫽n, is constant. Therefore, d ⵺ (X p (t)) is either concave or constant with respect to t僆T, since d i (x 1 (t)) is concave on e 1 . In summary, we have that d i (X p (t)) ⫽d (n) (X p (t)) is a concave function for t僆T,n⫽1,..., M. Moreover, since the inequality d (n) (X p (t)) ⬍d (n⫹1) (X p (t)), n ⫽1,..., M⫺1, holds for all t僆T, it follows that the order of the distance functions does not change. As a result, OM ⌳ (X p (t)) is also concave in the interval T. Assume w.l.o.g. that the objective function is nonincreasing for t ⬍0. Hence, we may decrease tគuntil either x 1 (t)僆ᐂor d (k) (X p (t)) ⫽d (k⫹1) (X p (t)). Now, we prove that the two assumptions made on X p do not imply any loss of generality: (i) Let n僆{1, 2, . . . , M⫺1} such that d i (X p ) ⫽d (n) (X p )⫽d (n⫹1) (X p )⫽d j (X p ), where i:⫽(n) and j:⫽(n⫹1). Note that n⫽k, since, otherwise, X p would satisfy (2). Hence, the elements d i (X p ) and d j (X p ) possibly swap positions in the vector d ⱕ (X p (t)), that is, d i (X p (t)) ⱕd j (X p (t)) for tⱕ0 and d i (X p (t)) ⬎d j (X p (t)) for t⬎0. However, both functions d i (X p ) and d j (X p ) are still concave with respect to t僆Tand both are still multiplied by the same ⌳value, aor b (since n⫽k). Therefore, this change has no influence on the concavity and the slope of the objective function OM ⌳ (X p (t)). (ii) Concerning the reallocation of nodes, let v i 僆ᐂbe a node such that w i d(v i ,x 1 )⫽w i d(v i ,x l ) holds for another solution point x l ⫽x 1 and x 1 is not the bottleneck point of this node on edge e 1 . (Otherwise, the allocation will not change with respect to x 1 (t), t僆T.) One of the following two cases can occur: 1. v i is allocated to x 1 (t) for tⱕ0 and to x l ,l⫽2,..., p, for t⬎0. Thus, we have d i (X p (t)) ⫽d i (x 1 (t)) for t ⱕ0 on edge e 1 and d i (X p (t)) ⫽d i (x l ), t⬎0, on edge e l . To be reallocated, the distance function of v i on edge e 1 ,d i (x 1 (t)) has to be increasing for tⱕ0. After the change of allocations, we obtain d i (X p (t)) ⫽d i (x l )on e l , which is constant with respect to t. (See the two leftmost edges of Fig. 3.) Thus, d i (X p (t)) is concave for t僆T. 2. v i is allocated to x l for tⱕ0 and to x 1 (t) for t⬎0. As above, d i (X p (t)) is concave for t僆Tsince it is the minimum of a linear and a constant function (see the two edges on the right-hand side of Fig. 3). ■ Note that the above result does not hold if one or more 4 NETWORKS—2003 F3 tapraid5/8u-netwrk/8u-netwrk/8u0103/8u0227-03a deangeln S⫽18 11/18/02 20:49 Art: 1053 Input-ljs(ljs) node weights are negative. In this case, d i (X p (t)) may be convex with respect to tand, hence, the ordered median function may no longer be concave in the interval T. From Lemma 1, it follows that we can move an arbitrary solution point on its edge either to the left or to the right without increasing the objective function value until a point is attained for which (2) holds. This is illustrated in the following example continuing the discussion preceding Lemma 1. Example 2. Consider the network of Example 1and the initial solution X 2 ⫽{x 1 ⫽([v 1 ,v 2 ], 11 12), x 2 ⫽([v 5 ,v 7 ], 3 8)}. For ⌳ 7 ⫽(0.2, 0.2,...,0.2, 1), it is possible to improve the objective function value by moving the point x 1 to the left up to the point ([v 1 ,v 2 ], 10 12). This yields d (7) (X 2 (⫺1 12)) ⫽d 7 (x 2 ) ⫽5⫽d 1 (x 1 (⫺1 12)) ⫽d (8) (X 2 (⫺1 12)). Hence, (2) holds. In the previous lemma, we could choose a single solution point and move it along its edge until condition (2) was fulfilled. Obviously, we can repeat this procedure for all points in X p . This leads to the following corollary: Corollary 2. Let X p ⫽{x 1 ,...,x p }債ᏼ(Ᏻ)be a solution to the ordered p-median problem with nonnegative node weights,pⱖ2and ⌳ k 僆⺢ 0⫹ M ,1ⱕkⱕM⫺1. Then,there exists a solution X⬘ p with OM ⌳ (X⬘ p )ⱕOM ⌳ (X p )such that either X⬘ p 債ᐂor d (k) (X⬘ p )⫽d (k⫹1) (X⬘ p )holds. Proof. Assume that X p 債ᐂand d (k) (X p )⬍d (k⫹1) (X p ). Then, according to Lemma 1, we start by moving one solution point after the other until we obtain a new solution X⬘ p where either all solution points are nodes or finally d (k) (X⬘ p )⫽d (k⫹1) (X⬘ p ) holds. ■ In the following, we will deal with the difficulties which occur when the k th and (k⫹1) st vertices in the ordered vector of the distance functions have the same value. Resolving these difficulties will lead us to the proof of the FDS. We first give a formalized description of the set of solution points addressed in the second part of the characterization of our FDS introduced at the beginning of this section. For every point in X* p ⶿(ᐂ艛Ᏹᏽ), there exists another solution point in X* p 艚(ᐂ艛Ᏹᏽ) and two nodes allocated to each of the two points such that the weighted distances of these nodes to their respective solution points are equal. Define the set of ranges (canonical set of distances) ᏾債⺢ ⫹ by ᏾:⫽兵r僆⺢⫹兩᭚EQ 僆EQij :di共EQ兲⫽r⫽dj共EQ兲 or ᭚vi,vj僆ᐂ,vi⫽vj:r⫽wid共vj,vi兲其. Ranges correspond to function values of equilibria or to node-to-node distances. In terms of the general characterization of the FDS, let R⬘be the set of ranges of the points in X* p 艚(ᐂ艛Ᏹᏽ). Then, for every other solution point x not in this set there exists a node v i allocated to xand a range r僆R⬘such that w i d(x,v i )⫽r. This is now generalized as follows: Definition 3. Let ᏺ⫽(Ᏻ,l)be an undirected network with nonnegative node weights and the set ᏾as defined above.A point x ⫽(e,t)is called an r-extreme point or pseudoequilibrium with range r 僆᏾if there exists a node v i 僆ᐂwith r ⫽w i d(x,v i ). Let us denote by ᏼᏱᏽ the set of all pseudoequilibria with respect to all ranges r僆᏾. Note that ᐂ債ᏼᏱᏽ, which follows directly from the above definition, and also that Ᏹᏽ 債ᏼᏱᏽ, since every equilibrium EQ 僆EQ ij of two nodes v i and v j is an r-extreme point with r⫽d i (EQ) ⫽d j (EQ). The above definition generalizes a concept introduced in Pe´rez-Brito et al. [16]. Example 3. The set of ranges on the edge [v 1 ,v 2 ]of the network given in Example 1is {0, 1, 2, 2.6, 3, 4, 6} (see Fig. 2). The point x*⫽([v 1 ,v 2 ], 2 3)is a pseudoequilibrium of range 4. Our goal is to prove that ᏼᏱᏽ is an FDS for the ordered p-median problem with pⱖ2 and ⌳ k 僆⺢ 0⫹ M ,1ⱕkⱕM ⫺1. In addition, any optimal solution X* p must satisfy X* p 艚(ᐂ艛Ᏹᏽ)⫽A. The first result proves the existence while the latter allows us to identify an FDS for any given problem. Using Lemma 1, we could move an arbitrary solution point along its edge to the left or to the right until we have d (k) (X p )⫽d (k⫹1) (X p ). The goal is to find a method to continue this process without increasing the objective funcFIG. 3. v i changes its allocation from x 1 (t)tox l , respectively, from x l to x 1 (t). NETWORKS—2003 5 tapraid5/8u-netwrk/8u-netwrk/8u0103/8u0227-03a deangeln S⫽18 11/18/02 20:49 Art: 1053 Input-ljs(ljs) tion value. If we are in this situation of equality, the idea is to move more than one solution point simultaneously, preserving the relationship d (k) (X p )⫽d (k⫹1) (X p ) and the permutation of the distance functions at the positions kand k⫹1. In Example 2, we have d (7) (X 2 (⫺1 12)) ⫽5 ⫽d (8) (X 2 (⫺1 12)). Here, we can continue moving x 1 to the left if we simultaneously move x 2 to the right in such a way that d (7) (X 2 ⵺)⫽d (8) (X 2 ⵺) is preserved. Before formalizing this approach, we introduce additional notation. Observe that we stop moving a point if, for two vertices v (k) and v (k⫹1) , we had r k :⫽d (k) (X p ) ⫽d (k⫹1) (X p ). But, obviously, there may be more than two nodes allocated to solution points whose weighted distance to their respective points is r k . Therefore, let X p ⫽{x 1 ,..., x p }債ᏼ(Ᏻ) be a solution to the ordered p-median problem with X p 債ᐂand d (k) (X p )⫽d (k⫹1) (X p ) ⫽r k ,r k 僆᏾.Define nគ,n៮as the two indices with 1 ⱕnគ ⱕk⬍k⫹1ⱕn៮ⱕMsuch that d共nគ⫺1兲共Xp兲⬍d共nគ兲共Xp兲⫽···⫽rk⫽···⫽d共n៮兲共Xp兲 ⬍d共n៮⫹1兲共Xp兲, where d (0) (X p ):⫽⫺⬁and d (M⫹1) (X p ):⫽⫹⬁. Note that n៮⫺nគⱖ1, that is, nគ⬍n៮, by the assumption on X p . Furthermore, define X L 債X p as the (sub)set of points of X p such that for every x l 僆X L there exists a node v i 僆ᐂ allocated to x l with r k ⫽d i (x l )⫽d (n) (X p ) and (n)⫽i. W.l.o.g., we assume that X L :⫽{x 1 ,..., x L } consists of the first Lsolution points of X p ,1ⱕLⱕp. Note that, by assumption, Lⱖ2. Moreover, ᏹ L :⫽{1, . . . , L}. We first state a lemma for the special case n៮⫺nគ⫹1 ⬎L, which means that there exists a solution point xwhich has at least two nodes, v i and v j , allocated to it with weighted distance r k . In this case, x僆X p is an equilibrium of these two nodes, yielding x僆EQ ij . Therefore, it is possible to prove the FDS using the results of Lemma 1. Lemma 4. Let X p ⫽{x 1 ,...,x p }債ᏼ(Ᏻ)be a solution to the ordered p-median problem with nonnegative node weights,pⱖ2and ⌳ k 僆⺢ 0⫹ M ,1ⱕkⱕM⫺1. Then,there exists a solution X⬘ p with OM ⌳ (X⬘ p )ⱕOM ⌳ (X p )such that either n៮⫺nគ⫹1⫽L holds for the new solution or X⬘ p 債 ᏼᏱᏽ with X⬘ p 艚(ᐂ艛Ᏹᏽ)⫽A. Proof. Let X ៮ p ,pⱖ2, be a solution. Given X ៮ p ,we know from Corollary 2 that there exists another solution X p ⫽{x 1 ,..., x p }債ᏼ(Ᏻ), x l ⫽(e l ,s l ), l⫽1,..., p, with OM ⌳ (X p )ⱕOM ⌳ (X ៮ p ) such that X p 債ᐂor d (k) (X p ) ⫽d (k⫹1) (X p )⫽:r k . Note that if the former case holds the desired result follows. Let ᐂ X :⫽X p 艚ᐂand define ᏾ X as the set of ranges of the nodes in ᐂ X , that is: ᏾X:⫽ 再 兵r僆⺢兩᭚vi僆ᐂ,᭚vj僆ᐂX,vi⫽vj:r⫽wid共vi,vj兲其 if ᐂX⫽A Aotherwise. Now for X p let L,X L ,nគ, and n៮be defined as above and assume that n៮⫺nគ⫹1⬎L. Then, there exist x l 僆X L and v i ,v j 僆ᐂ,v i ⫽v j , such that d (n 1 ) (X p )⫽d i (x l )⫽r k ⫽d j (x l )⫽d (n 2 ) (X p ), where (n 1 )⫽i,(n 2 )⫽j, and v i and v j are both allocated to x l (with respect to X p ). Thus, x l 僆EQ ij is an equilibrium of the two nodes v i and v j with range r k . As a result, r k 僆᏾ and all the points of the set X L are r k -extreme points. Let x m 僆X p ⶿(X L 艚ᐂ X ). Using the same arguments as in Lemma 1, we can fix all other solution points and just move x m 3 x m (t) on its edge until x m (t) is a node or d i (x m (t)) ⫽:r 僆({r k }ᐃ᏾ X )債᏾for some node v i allocated to x m (t). In this case, x m (t) is a pseudoequilibrium with range r. This procedure can be applied to all solution points not belonging to X L 艛ᐂ. It is also obvious that for those solution points x l 僆ᐂ X 艚X L the above procedure can be applied. Therefore, if n៮⫺ nគ⫹1⬎L, we have X p 債ᏼᏱᏽ and X p 艚(ᐂ艛Ᏹᏽ) ⫽Aand the desired result follows. ■ Lemma 4 characterizes an FDS for the ordered p-median problem with ⌳ k ⫽(a,..., a,b..., b) except for n៮⫺ nគ⫹1⫽L. Dealing with this case will finally complete the identification of the FDS. Here, we really have to move solution points simultaneously in order to find a nonascent direction for the objective function. Theorem 5. The ordered p-median problem with nonnegative node weights,pⱖ2and ⌳ k 僆⺢ 0⫹ M ,1ⱕkⱕM ⫺1, always has an optimal solution X* p 債ᏼ(Ᏻ)in the set ᏼᏱᏽ.Moreover,X* p 艚(ᐂ艛Ᏹᏽ)⫽A. Proof. Let X ៮ p ,pⱖ2, be an optimal solution. We know from Lemma 4 that there exists another optimal solution X p ⫽{x 1 ,..., x p }債ᏼ(Ᏻ), x l ⫽(e l ,s l ), l ⫽1,...,p, with OM ⌳ (X p )⫽OM ⌳ (X ៮ p ) such that either n៮ ⫺nគ⫹1⫽Lholds for the new solution or X p 債ᏼᏱᏽ with X p 艚(ᐂ艛Ᏹᏽ)⫽A. Note that if the latter case holds the desired result follows. Consider for X p the elements ᐂ X ,᏾ X ,L,X L ,nគ, and n៮as defined above. Now, we analyze the case n៮⫺nគ⫹1⫽L. Observe that ᐂ X 艚X L ⫽A(see the proof of Lemma 4). Thus, for every x l 僆X L there exists a unique v i l 僆ᐂallocated to x l with d i l (x l ) ⫽r k . First, we assume that (i)d (n) (X p )⫽d (n⫹1) (X p ) for all n僆{1, . . . , M}⶿({M} 艛{nគ,..., n៮}), (ii) None of the solution points x l 僆X L is a bottleneck point of some node v i 僆ᐂ, and 6 NETWORKS—2003 tapraid5/8u-netwrk/8u-netwrk/8u0103/8u0227-03a deangeln S⫽18 11/18/02 20:49 Art: 1053 Input-ljs(ljs) (iii)/ ?v i 僆ᐂ:w i d(v i ,x l 1)⫽w i d(v i ,x l 2), that is, no node is at the same distance from two solution points x l 1,x l 2僆X p . Define for t僆⺢:X p (t):⫽{x 1 (t/ⵜ 1 ),..., x L (t/ⵜ L ), x L⫹1 ,..., x p }, where ⵜ l :⫽⫾w i l l(e l ) is the slope of the distance function d i l ⵺of node v i l at the point x l on edge e l , and x l (t/ⵜ l ):⫽(e l ,s l ⫹(t/ⵜ l )), l⫽1,...,L. Note that the distance functions d i l ⵺are all linear in a sufficiently small interval around the points x l . Otherwise, x l would be a bottleneck point of node v i l . Let T:⫽[tគ,t ៮]僆⺢be an interval with tគ⬍0⬍t ៮and s l ⫹(t/ⵜ l )僆(0, 1), @l僆ᏹ L ,t僆T, such that (i) and (iii) hold for X p (t) and (ii) for x l (t/ⵜ t ), 1 ⱕlⱕL, for all t僆T. This interval exists since (i), (ii), and (iii) hold for t ⫽0 and all distance functions d i ⵺⫽w i d(䡠,v i ) are continuous on any edge. Let nⰻ{nគ,..., n៮} and v i ⫽v (n) . By the above assumptions on X p and the definition of T, we have that d (n) (X p (t)) ⫽d i (x l (t/ⵜ l )), for all t僆T,ifv i is allocated to x l 僆X L and d (n) (X p (t)) ⫽d i (x l )ifv i is allocated to a solution point in X p ⶿X L . In both cases, d (n) (X p (t)) is linear with respect to t僆T. On the other hand, let n 1 ,n 2 僆{nគ,...,n៮}, n 1 ⫽n 2 , and let node v (n 1 ) ⫽:v i and node v (n 2 ) ⫽:v j be allocated to x l 1 and x l 2 , respectively. By the definition of T, we have that x l 1 ,x l 2 僆X L . Note that x l 1 ⫽x l 2 , since n៮⫺nគ⫹1 ⫽L. Thus, di 冉 xl1 冉 t ⵜl1 冊冊 ⫽di共xl1兲⫹sgn共ⵜl1兲wi tl共el1兲 ⵜl1 ⫽d共n1兲共Xp兲⫹t⫽rk⫹t⫽d共n2兲共Xp兲⫹t ⫽dj共xl2兲⫹sgn共ⵜl2兲wj tl共el2兲 ⵜl2 ⫽dj 冉 xl2 冉 t ⵜl2 冊冊 for all t僆T, where sgn( x) is the sign function of x. Hence, d i (x l 1 (t/ⵜ l 1 )) ⫽d (n 1 ) (X p (t)) ⫽d (n 2 ) (X p (t)) ⫽d j (x l 2 (t/ⵜ l 2 )), @t僆T, and we are increasing or decreasing r k by 兩t兩. This means that we are simultaneously moving each solution point x l 僆X L on e l by x l 3x l (t/ⵜ t ), while preserving the relationship d (nគ) (X p (t)) ⫽...⫽d (n៮) (X p (t)). See Figure 4 for an example with nគ⫽kand n៮⫽k⫹1. As a result, all entries d (n) (X p (t)) are linear with respect to t僆T. This fact together with the assumption that d (n) (X p (t)) ⫽d (n⫹1) (X p (t)), @t 僆T,n僆{1,...,M}⶿({M}艛{nគ,...,n៮}), implies that the objective function OM ⌳ (X p (t)) is also linear with respect to t 僆Tand, hence, constant over T, since X p ⫽X p (0) is already optimal. Consequently, any X p (t) with t僆Tis also optimal. In summary, the objective function OM ⌳ (X p (t)) is constant over the interval Tand we can either decrease tគor increase t ៮by an arbitrarily small value without changing the objective function value OM ⌳ (X p (t)). Assume w.l.o.g. that we increase t ៮. Then one of the following two cases can occur: r k ⫹t ៮僆᏾ X :Then, either x l (t ៮/ⵜ l )⫽v i 僆ᐂis a node for some l僆ᏹ L or x l (t ៮/ⵜ l ) is an equilibrium EQ ij of two nodes v i and v j which are both allocated to x l (t ៮/ⵜ l ) such that d (n 1 ) (X p (t ៮)) ⫽d i (x l (t ៮/ⵜ l )) ⫽r k ⫹t ៮⫽d j (x l (t ៮/ⵜ l )) ⫽d (n 2 ) (X p (t ៮)), where v i ⫽v (n 1 ) and v j ⫽v (n 2 ) . Then, all the remaining points x l (t ៮/ⵜ l ), l僆ᏹ L , are pseudoequilibria with range r k ⫹t ៮. In the latter case, we extend ᏾ X by the ranges of v i . Now, we can, again, as already described above, move the remaining solution points x m 僆X p ⶿X L independently from each other until we obtain a new optimal solution X* p 僆ᏼᏱᏽ such that all solution points are pseudoequilibria with respect to a range of one of the points in X* p 艚(ᐂ艛Ᏹᏽ). r k ⫹t ៮ⰻ᏾ X : In this case, a solution point x l 僆X p ⶿X L must exist together with a node v i l allocated to x l [with respect to X p (t ៮)] such that d (n) (X p (t ៮)) ⫽d i l (x l )⫽r k ⫹t ៮, where v i l ⫽v (n) . We redefine X L :⫽X L 艛{x l } and also X p (t ៮) :⫽{x 1 (t/ⵜ 1 ),..., x L⫹1 (t/ⵜ L⫹1 ), x L⫹2 ,..., x p }, where w.l.o.g. l⫽L⫹1. Then, we can apply the same argument as above in order to move the L⫹1 solution points simultaneously. Now, we show that the assumptions (i)–(iii) previously made for X p do not imply any loss of generality: (i) As in Lemma 1, a possible swap of the elements in the vector d ⱕ (X p ) has no influence on the slope of the objective function OM ⌳ (X p (t)). (ii)Ifx l 僆X L would be a bottleneck point of some node v i allocated to x l , then the distance function of this node d i (x l (t/ⵜ l )) ⫽d (n) (X p (t)), v i ⫽v (n) , would be concave with respect to tand, therefore, also OM ⌳ (X p (t)), that is, we could find a descent direction for t, which contradicts the assumption that X p is optimal. (iii) Let v i 僆ᐂbe a node such that w i d(v i ,x l 1)⫽w i d(v i , x l 2), that is, v i possibly changes its allocation between the solution points x l 1and x l 2for t⬍0ort⬎0, where one or both points are in X L , w.l.o.g. x l 1僆X L . (Otherwise, x l 1and x l 2are fixed with respect to t僆T.) But, similar to Lemma 1, a reallocation of v i 僆ᐂ from, w.l.o.g., the solution point on e l 1to the solution point on edge e l 2can only occur if the distance function of node v i on e l 1, that is, d i (x l 1(t/ⵜ 1 )), has, with FIG. 4. Simultaneous movement of x l 1and x l 2on e l 1and e l 2. NETWORKS—2003 7 F4 tapraid5/8u-netwrk/8u-netwrk/8u0103/8u0227-03a deangeln S⫽18 11/18/02 20:49 Art: 1053 Input-ljs(ljs) respect to t, a greater slope than has d i (x 2 (t/ⵜ 2 )) on edge e 2 . Hence, the function d (n) (X p (t)) ⫽d i (X p (t)), v (n) ⫽v i , is concave over Tfor some n⫽1,...,M, which leads again to a contradiction to the optimality of X p .■ Example 4. Consider the situation of Example 2. We have nគ⫽7and n៮⫽8. Hence,n៮⫺nគ⫹1⫽2⫽L.Starting with X 2 ⫽{x 1 ,x 2 }, where x 1 ⫽([v 1 ,v 2 ], 10 12)and x 2 ⫽([v 5 ,v 7 ], 3 8), we have i 1 ⫽1and i 2 ⫽7. Define X 2 (t):⫽{x 1 (t/6), x 2 (t/⫺8)}. If t is negative we strictly decrease the objective function value.Finally,for t ⫽⫺1, we obtain the optimal solution X* 2 ⫽{x*⫽([v 1 ,v 2 ], 2 3), EQ 57 57 ⫽([v 5 ,v 7 ], 1 2)}. Since ᏼᏱᏽ is an FDS for the ordered p-median problem with ⌳⫽(a,..., a,b..., b), a natural question that arises now refers to the number of elements contained in the set ᏼᏱᏽ. Taking K⫽兩Ᏹᏽ兩and M⫽兩ᐂ兩, we obtain a range rfor every equilibrium and every pair of nodes u,v 僆ᐂ,u⫽v, yielding in total 兩᏾兩⫽O(K⫹M 2 ) ranges. Since every distance function d i ⵺can assume a value r 僆᏾in at most two points on an edge e僆Ᏹ, we have O(NM)r-extreme points and as a result 兩ᏼᏱᏽ兩⫽ O(NM(K⫹M 2 )). From the above results, it is possible to devise an algorithm to solve the ordered p-median problem exactly. The new algorithm generalizes the one proposed by Pe´rez-Brito et al. [16] and will be presented in the next section. 2.1. An Algorithm for Solving the Ordered p-Median Problem with ⌳ k -Vector By Theorem 5, there always exists an optimal solution in which one of the points (e.g., x p ) is a node or an equilibrium point. From the proof of the theorem, it follows that all the other solution points are either nodes or pseudoequilibria with respect to the range of the equilibrium or one of the ranges of the node(s). Hence, we first compute the set of equilibria Ᏹᏽ, then the ranges ᏾, and afterward the rextreme points for every r僆᏾. The latter must be saved with a reference to rin a set ᏼᏱᏽ[r]. Next, we choose a candidate x p from the set ᐂ艛Ᏹᏽ.Ifx p 僆EQ ij is an equilibrium of range r⫽d i (x p )⫽d j (x p ), then the objective function value OM ⌳ (X p⫺1 艛{x p }) is determined for all p⫺1 subsets X p⫺1 ⫽{x 1 ,..., x p⫺1 }ofᐂ艛 ᏼᏱᏽ[r]. If x p ⫽v i is a node, then the set ᏾ v i is computed (see proof of Theorem 5). Furthermore, for all subsets X p⫺1 ⫽{x 1 ,..., x p⫺1 }ofᐂ艛{ᏼᏱᏽ[r]兩r僆᏾ v i }, the objective function value OM ⌳ (X p⫺1 艛{x p }) must be determined. A summary of the steps required to find an optimal solution of the ordered p-median problem with ⌳ k 僆⺢ 0⫹ M , 1ⱕkⱕM⫺1 is given below: Algorithm 2.1 Computation of an optimal solution set X* p Input: Network ᏺ⫽(Ᏻ,l), distance-matrix D,pⱖ2, and a vector ⌳ r ⫽(a,...,a,b,...,b), 1 ⱕrⱕM⫺1 Output: An optimal solution set X* p 1. Initialization Let X* p :⫽A,res :⫽⫹⬁ 2. First compute Ᏹᏽ, then the set of ranges ᏾, and based on these sets, determine for every r 僆᏾the rextreme points and save them with a reference to r in a set ᏼᏱᏽ[r]. 3. FORALL EQ 僆Ᏹᏽ DO Let x p :⫽EQ 僆EQ ij and compute the range r of the equilibrium, i.e., r :⫽d i (EQ)⫽d j (EQ). FORALL X p⫺1 ⫽{x 1 ,..., x p⫺1 }債ᐂ艛 ᏼᏱᏽ[r]DO Compute OM ⌳ (X p ), where X p :⫽X p⫺1 艛{x p }. IF OM ⌳ (X p )⬍res THEN X* p :⫽{X p }, res :⫽OM ⌳ (X* p ) 4. FORALL v i 僆ᐂDO Let x p :⫽v i and compute the set ᏾ v i of all ranges of the node. FORALL X p⫺1 ⫽{x 1 ,..., x p⫺1 }債ᐂ艛 {ᏼᏱᏽ[r]兩r僆᏾ v i }DO Compute OM ⌳ (X p ), where X p :⫽X p⫺1 艛{x p }. IF OM ⌳ (X p )⬍res THEN X* p :⫽{X p }, res :⫽OM ⌳ (X* p ) 5. RETURN X* p The above algorithm has complexity O(pN p⫺1 M p log M(K⫹M p )). To show this, observe that the computation of the equilibria set Ᏹᏽ is possible in O((NM ⫹K)log M) steps. If we integrate the computation of the range of an equilibrium and a node in the line-sweep algorithm, then the complexity for obtaining the set ᏾is O(K⫹M 2 ), where it is possible to compute ᏼᏱᏽ in O(NM(K⫹M 2 )). In Steps 3 and 4, we have to evaluate the objective function for a node or an equilibrium for all subsets of size p⫺1ofᐂ艛 ᏼᏱᏽ[r] and ᐂ艛{ᏼᏱᏽ[r]:r僆᏾ v i }, respectively. In the first case, we have O(( p⫺1 M⫹MN )) ⫽O((MN) p⫺1 ) and, in the second case, O(( p⫺1 M⫹(M⫺1)MN )) ⫽O((M 2 N) p⫺1 ) different subsets (兩᏾ v i 兩⫽M⫺1). Since the evaluation of the objective function takes O(pM log M) time [because it is no longer possible to compute the ordered vectors d ⱕ (X p )a priori in the line-sweep algorithm], we obtain for Steps 3 and 4 the complexity O共pM log M共K共MN兲p⫺1⫹M共M2N兲p⫺1兲兲 ⫽O共pNp⫺1Mplog M共K⫹Mp兲兲, which is the total complexity of the algorithm. It is clear that these problems are NP-hard because the p-median and p-center problems are particular instances. Due to this reason, we may have to apply approximation algorithms in order to solve the problem. 8 NETWORKS—2003 tapraid5/8u-netwrk/8u-netwrk/8u0103/8u0227-03a deangeln S⫽18 11/18/02 20:49 Art: 1053 Input-ljs(ljs) The recent papers by Charikar et al. [2], Jain and Vazirani [9], and Charikar and Guha [3] provide constantfactor approximation algorithms for the p-median problem. At this point, it is not yet clear whether the techniques in those papers can be applied (with the necessary adjustments) to the ordered p-median problem with ⌳-modeling weights. In the next section, we show how to solve the ordered p-median problem with ⌳-modeling weights on tree graphs in polynomial time. This development is important because it can be applied to approximate such problems in general graphs. In Bartal [1] and Charikar et al. [2], O(log Mlog log M) approximation algorithms are given for the p-median problem. These algorithms are based on solving p-median problems on a family of trees. (The general network metric is approximated by the tree metrics.) The same approach can be applied to the ordered p-median problem with ⌳-modeling weights. Therefore, polynomial time algorithms for solving that problem on trees are useful to derive O(log Mlog log M) approximating solutions for ordered p-median problems on general networks. 3. A POLYNOMIAL ALGORITHM FOR THE ORDERED p-MEDIAN PROBLEM ON TREE NETWORKS In this section, we solve the ordered p-median problem with at most two types of ⌳-weights 关⌳ ⫽共a,M⫺s ···,a,b, s ···, b)] in polynomial time on a tree. To do that, we adapt and modify the dynamic algorithm for the p-centdian model on a tree proposed in Tamir et al. [24]. Assume that we are given a tree ᐀with 兩ᐂ兩⫽M. Using the discretizing result, it is clear that the optimal ordered p-median set can be restricted w.l.o.g. to the set Y ⫽ᏼᏱᏽ. Once we restrict to trees, the set Yis of cardinality O(M 4 ) (notice that 兩Ᏹ兩⫽M⫺1). Computing and augmenting these points into the node set of ᐀has complexity O(M 4 ) by the procedure in Kim et al. [11]. Let ᐀ a denote the augmented tree with the node set Y. Each point in Yis called a seminode. In particular, a node in ᐂis also a seminode. Suppose now that the given tree ᐀⫽(ᐂ,Ᏹ), 兩ᐂ兩⫽M and 兩Ᏹ兩⫽M⫺1, is rooted at some distinguished node, say, v 1 . For each pair of nodes v i ,v j , we say that v i is a descendant of v j if v j is on the unique path connecting v i to the root v 1 .Ifv i is a descendant of v j and v i is connected to v j with an edge, then v i isachild of v j and v j is the (unique) father of v i . If a node has no children, it is called a leaf of the tree. As shown in Tamir [22], we can now assume w.l.o.g. that the original tree is a binary tree, where each nonleaf node v j has exactly two children, v j(1) and v j(2) . The former is called the left child, and the latter, the right child. For each node v j ,ᐂ j will denote the set of its descendants. Once the tree ᐀ a has been obtained, a second preprocessing phase similar to the used in Tamir et al. [24] is performed. For each node v j , we compute and sort the distances from v j to all seminodes in ᐀ a . Let this sequence be denoted by L j ⫽{r j 1 ,..., r j m }, where r j i ⱕr j i⫹1 ,i ⫽1,...,m⫺1, and r j 1 ⫽0. We can assume w.l.o.g. that there is a one-to-one correspondence between the elements in L j and the seminodes in Y(Tamir et al. [24]). The seminode corresponding to r j i is denoted by y j i ,i⫽1,...,m. We note that the total computational effort of this phase is O(M 6 ) and can be achieved by using the centroid decomposition approach as in Kim et al. [11] or the procedure described in Tamir [22]. For each node v j , an integer q⫽0, 1, . . . , p,r j i 僆L j , an integer l⫽0, 1, 2 . . . , s, and cbeing a weighted distance from any node to a seminode, let G(v j ,q,r j i ,l,c) be the optimal value of the subproblem defined on the subtree ᐀ j , given that a total of at least one and at most q seminodes (service centers) can be selected in ᐀ j . Moreover, we assume that at least one of them is located in {y j 1 ,...,y j i }艚Y j , that exactly lvertices are associated to b ␭ -weights, and that the minimal distance allowed for an element with a b ␭ -weight is c(in the above subproblem, we implicitly assume no interaction between the seminodes in ᐀ j and the rest of the seminodes in ᐀). The function G(v j , q,r,l,c) is computed only for qⱕ兩ᐂ j 兩, where ᐂ j is the node set of ᐀ j ,lⱕmin(s,兩ᐂ j 兩) (notice that a larger l would not be possible), and if l⬎0, then cⱕmax{w k d(v k , y)兩v k 僆ᐂ j and y僆Y j }. Also, for each node v j we define G共vj,0,r,0,c兲⫽⫹⬁. Analogously, G(v j ,q,r,l,c)⫽⫹⬁for any combination of parameters that leads to an infeasible configuration. Similarly, for each node v j , an integer q⫽0, 1, . . . , p, r j 僆L j , an integer l⫽0, 1, 2 . . . , s, and cbeing a weighted distance from any node to a seminode, we define F(v j ,q,r j ,l,c) as the optimal value of the subproblem defined in ᐀ j satisfying the following conditions: 1. A total of qservice centers can be located in ᐀ j ; 2. There are already some selected seminodes in Y⶿Y j and the closest among them to v j is at a distance r j ; 3. There are exactly lⱕmin{兩ᐂ j 兩,s} vertices with b ␭ -weight in ᐀ j ; and 4. cis the minimal weighted distance allowed for a weighted distance with a b ␭ -weight. Obviously, the function Fis only computed for those r j i that correspond to y j i 僆Y⶿Y j . The algorithm computes the function Gand Fat all the leaves of ᐀and then, recursively, proceeding from the leaves to the root, computes these functions at all nodes of ᐀. The optimal value of the problem will be given by min c G共v1,p,r1 m,s,c兲, NETWORKS—2003 9 tapraid5/8u-netwrk/8u-netwrk/8u0103/8u0227-03a deangeln S⫽18 11/18/02 20:49 Art: 1053 Input-ljs(ljs)