THE BI-CRITERIA DOUBLY WEIGHTED CENTER-MEDIAN PATH PROBLEM ON A TREE J. Puerto, A.M. Rodriguez-Chia, A. Tamir, & D. Perez-Brito Presenter: 陳思佑 鄭仲鈞 吳佳欣 高新綸 2007.06.13

Outline Abstract Critical value for the weighted path center problem Obtaining the weighted center-median non-dominated set The non-dominated set with length constraint

Abstract Presenter: 陳思佑

Problem Given Consider a path P, P in PL T: a tree network with n node P*: a given subset of simple path in T PL: the subset of all discrete paths (length < L) Consider a path P, P in PL P: a path-shaped facility Tree node: the customers How to calculate the total transportation cost from customers to facility

From title… 5 THE BI-CRITERIA DOUBLY WEIGHTED CENTER-MEDIAN PATH PROBLEM ON A TREE Doubly weighted Node: center-weight u, median-weight w (nonnegative) Bi-criteria Weighted path center criterion maximum center-weighted distance MAX(P) = max ubd(vb, p), vb in V Weighted path median criterion sum of the median-weighted distance SUM(P) = Σ wbd(vb, p), b = 1 to n

Path: (MAX(P), SUM(P)) View as a outcome space Path P -> (MAX(P), SUM(P)) Finding all the non-dominated point Form a set, NDO(P*) P is non-dominate, if no path P’ MAX(P’) <= MAX(P), SUM(P’) <= SUM(P) MAX(P’) + SUM(P’) < MAX(P) + SUM(P) SUM(P) MAX(P)

In this paper # of efficient paths: Ω(n2) 7 # of efficient paths: Ω(n2) At most 2n non-dominated outcome Generate in O(nlogn) optimal time SUM(P) MAX(P)

Solve other model Cent-dian model Restricted model Objective: convex combination of weighted center and weighted median function Restricted model Objective: minimize one of MAX or SUM, subject to an upper bound on the other one After the set of non-dominated outcome has been obtained, all these problems are solve in linear time Overall, O(nlogn)

Summary of results

Critical value for the weighted path center problem Presenter: 陳思佑

Critical value A path P, vk in P For P, if the maximum center-weighted distance to P is attained at vk, vk is critical Max ubd(vb, P) = max ubd(vb, vk) Compute the set of all the critical value => compute all the different MAX(P) Will prove that the cardinality is at most 2n => |NDO(P*)| <= 2n Path P vk vb longest

In this problem T = (V, E) V = {v1, …, vn} E = {e2, …, en} An edge ej is identified as an interval of length lj, We can refer to its interior points, continuous Discrete path The endpoints of path are nodes of T, not arbitrary point e2 v2

Continuous weighted 1-center problem v1 = cu Min max ubd(x, vb) = max ubd(cu, vb) cu can be obtained in O(n), center Add cu, and assume T is rooted at cu Identifies bottleneck nodes, vs, vt v1 in Pst, usd(vs, v1) = utd(vt, v1) = max uid(vi, v1) S ~> t, diameter v2 vt vs

Consider any pair of subtrees, Ts and Tt vs in Ts, vt in Tt v1 = cu Consider any pair of subtrees, Ts and Tt vs in Ts, vt in Tt Ts∩Tt = {v1}, Ts∪Tt = T 3 sets Ps = {P in P*, P in Ts} Pt = {P in P*, P in Tt} P’ = {Pij in P*, vi in Ts, vj in Tt} v2 vt vs Tt Ts

Theorem A denote the set of distinct MAX(P) for all path P |A| <= 2n

Prove (1) |P*| <= n(n+1)/2 Pij in P’ can be represented as the union of Pi1, Pj1 βsi = max ukd(vk, Pi1), vk in Ts βtj = max ukd(vk, Pj1), vk in Tt MAX(Pij) = max(βsi, βtj) v1 = cu v2 vt vs Tt Ts

Prove (2) P in Ps v1 is a continuous weighted center Let vk be the closet node to v1 in P MAX(P) = max uad(va, vk), vk is critical Define δk = max uad(va, vk) MAX(P) is an element in {δk: vk in Ts} P in Pt, same v1 = cu vk v2 vt vs Tt Ts

Prove (3) P’: MAX(Pij) = max(βsi, βtj) Ps: MAX(P) is an element in {δk: vk in Ts} Pt: MAX(P) is an element in {δk: vk in Tt} βsi = max ukd(vk, Pi1), vk in Ts βtj = max ukd(vk, Pj1), vk in Tt δk = max uad(va, vk) Define A* = {βsi: vi in Ts} ∪{βtj: vj in Tt} ∪{δk: vk in V} A <= A* n n

Conclusion The set A* is a superset of A We next refine the definition of a superset contaning A

Critical value for the weighted path center problem (2) Presenter: 鄭仲鈞

Notation Definition Optimal weighted path center : Ppq Optimal means:

Optimal path

Optimal path

Notation Definition Va(k) : vk這個節點，延path往下走的Children所構成的點集合。vk屬於Ppq上去除v1的點集合。

Notation Definition For v1: 分為Ts方向和Tt方向，分別是 For vp and vq: 因為已經走到path的末端 => Va(p)就直接相當於vp的Children的點集合 同理對vq也是一樣

Notation Definition γk : vk延path走下去，離vk最遠點和vk的距 離。即: γ1s , γ1t : 因為v1往path兩邊走都可，因此 有兩個γ值。即: 但因為v1是continuous weighted center point => γ1s =γ1t => 令γ1=γ1s =γ1t

Graph of γk , γ1s , γ1t

Notation Definition εs, εt : Ts和Tt上，離optimal path Ppq 最遠的點，到的距離Ppq。即: 根據定義，明顯的: MAX(Ppq) = max{εs, εt }

Graph of εs, εt

Properties of Ppq 此一性質即是說明，對任一點vk來說， 往path處走去的最遠Children的距離(γk)， 並且γk必定比εs, εt 還要大: Why?

Properties of Ppq 假若此性質不成立，代表 optimal path不再是optimal。 向走，才可以有效的減短 MAX(Ppq) = max{εs, εt } 也就是說，這是optimal path自然產生出的性質。 ”往path走的最遠子節 點，才有可能是其最 遠的子節點。”

Properties of Ppq Lemma:任何一條屬於P(端點跨過Ts-v1-Tt 的路徑之集合)的路徑，其Critical node _ Lemma:任何一條屬於P(端點跨過Ts-v1-Tt 的路徑之集合)的路徑，其Critical node 必定在Ppq之上。

Critical node

Proof 假設我們一行一行的看證明，那真的是 有點繁瑣: 所以，來個簡單的說明: 首先假設Critical node不在Optimal path上

The graph of proof 明顯的vm到vk比 vr到vk長，而根據 Ppq的特性， 也就是vg到vk應該要比 vr到vm長 =>vk才是真正的critical node. 和vr是critical node的假設 相矛盾

Conclusion of Ppq 既然所有屬於P的路徑，他們的Critical node 都在Ppq之上，那就代表Ppq之上的節點vk ， 它們所對應到的γk，以及εs, εt ，涵蓋了所 有可能的MAX(P)。若再加上之前Ps以及Pt ， 計算出來的MAX(P)之值域，即可形成A** :

Conclusion of Ppq 由Critical point看去 往γk走去的才可能是MAX(P) (往另外一個方向走較短) 就必定是εs或 εt (在P包含vp的狀況之下)

Generating A** 有演算法可以在O(n logn)的時間內產生 A**這個值域內的所有值。 假如是identical weighted的樹: =>可以在O(n)的時間內完成

Obtaining the weighted center-median non-dominated set 39 Presenter: 吳佳欣

To generate NDO(P*) we compute a planar set W = {(x,y)},satisfying |W|= O(n) and The set of first coordinate x of W = A** We’ll minimize SUM(P) under constraint MAX(P)=x

Example 8 (4,2) (3,7) 6 5 4 (2,7) 6 3 2 3 (1,4) 8 (3,3) 7 4 (5,6) 2 4 5 7 3 (3,2) 9 10 1 2 (2,9) (1,5) (2,2) (1,9)

Weighted center V1 (4,2) (3,7) 6 5 4 (2,7) 6 3 2 3 (1,4) 8 (3,3) 7 4 2.5 5.5 (4,2) (3,7) 6 5 4 (2,7) 6 3 2 3 (1,4) 8 (3,3) 7 4 (5,6) 2 4 5 7 3 (3,2) 9 10 1 2 (2,9) (1,5) (2,2) (1,9)

Weighted Path Center V1 (4,2) (3,7) 6 5 4 (2,7) 6 3 2 3 (1,4) 8 (3,3) 2.5 5.5 (4,2) (3,7) 6 5 4 (2,7) 6 3 2 3 (1,4) 8 (3,3) 7 4 (5,6) 2 4 5 7 3 (3,2) 9 10 1 2 (2,9) (1,5) (2,2) (1,9)

Critical Value for weighted path center problem δ0 100 δ1 80 δ2 85 δ3 70 δ4 65 δ5 50 δ6 54 δ7 60 δ8 72 δ9 87 δ10 78 γv1=37.5 V1 γ6=22 2.5 5.5 (4,2) (3,7) 6 5 γ5=30 4 (2,7) 6 3 2 γ8=10 3 (1,4) γ4=10 8 (3,3) 7 4 (5,6) 2 4 5 7 3 (3,2) 9 10 1 2 (2,9) (1,5) γ0=8 (2,2) (1,9)

Case 1: MAX(P)=δk If MAX(P)=δk, or The critical node vk of P (i.e. maxi ukd(vk,vi)=MAX(P)) is the closest point to weighted 1-center point. efficient path with critical node vk 應該是掛在vk上的一條帶子，往兩個最能減少SUM(P)的方向垂下。

Sum vi vi vj (vi, vj相鄰)

Sum vi vj 取min vb 從vi往vj走可以減少的SUM(P)值

SUM(P) Let SUM(P) be the minimum of all SUM(P’) of P’ with critical node vk and MAX(P’)=δk SUMt(), t=0,1,2,3. Can be compute in O(n) Time: O(Σv|Neighbor(v)|)=O(2n-2)=O(n) add (δk, SUM(P)) into W 前兩大 SUM3(vk,vb) 其實就是

Result V1 403 371 2.5 5.5 (4,2) (3,7) 6 5 4 (2,7) 6 3 2 595 3 (1,4) 8 (3,3) 547 7 676 4 (5,6) 2 4 5 7 3 622 740 (3,2) 9 10 1 2 (2,9) (1,5) (2,2) (1,9) 100 853 740 735

Case 2: MAX(P)=γk or {єs,єt} 如果MAX(P)= γk, 則P包含v1, critical node是P與path center交集的端點之一。 所以我們要查的是掛在Path(vk,vb)上, 從vk與vb垂下的路徑(vk, vb都在path center上, 且一個在Ts, 一個在Tt). 因為vk才是critical node, 所以γk>= γb. 設path center為Path(vp, vq) 把P從v1切開，只看Ts這半的話是Path(vi, v1), 從vk開始離開 Path(vp,v1), 以 表示 這類的Path中, 在Ts的 最小weight sum(另一半另外考慮)

(Continue.) Tt那邊也一樣。 這樣一來，MAX(P)= γk的最小SUM(P)就是 (方便起見，讓γp=max{єs, γp}, γq=max{єt, γq})

Compute Ss(vk) 利用SUM4(vk) = 計算Ss(vk) = (往SUM3最大的方向延伸) 由v1就不走Pp1

Compute SUM4(vk) Ex: SUM4(5) = SUM4(v1)+SUM0(5)-SUM0(4)-(2+2+2+9)*3 = 28 Ss(5) = SUM0(5) – SUM3(5,3)+SUM4(v1) = 129 – 28 = 101 t side is similar.

result W1={(100, 944) ,(80,740),(85,735), (70,676),(65,547),(50,403),(54,371), (60,622),(72,595),(87,853),(78,740)} W2={(γ4 =10,70),(γ5 =30,123), (γ1 =37.5,232.5),(γ1 =37.5,574), (γ6 =22,211),(γ8 =10,92)}

Time Complexity compute W2 = O(n) compute W1╭╮W2 = O(nlogn) |W| = O(n) from W find NDO(P*) = O(|W|log|W|) so the time complexity of finding NDO(P*) is O(nlogn)

The non-dominated set with length constraint 56 Presenter: 高新綸

5th section

Superset construction Where are the feasible paths in

Where Vk vk vj

Where Vk(i) vi

is the best value of the SUM objective by extending the path Pi1 towards Tt while maintaining Vk(i) as the critical node. MAX(Pij)=γk(i) L(Pij) ≦L Vk(i) vi vj

Obtain set in O(n logn) Compute MAXL(vk) = δk for all nodes vk ∈ V in O(n logn) time A. Tamir, "Sorting weighted distances with applications to objective function evaluations in single facility location problems," Operations Research Letters, vol. 32, pp. 249-257, May 2004. Compute {SUML(vk): vk ∈V } in O(n logn) time S. Alstrup, P. W. Lauridsen, P. Sommerlund, and M. Thorup, "Finding cores of limited length," in Algorithms and Data Structures. vol. 1272, 1997, pp. 45-54.

Obtain set in O(n logn) Only show one of the two sets, Two more notations .

Obtain set in O(n logn) {γk} is decreasing when we move vk from v1 to vp  va(1) = v2, va(2) = v3 …… vp = vm v2 v3 … … =vm

Compute in O(logn) γk >γm Vt(m) γk ≦γm vm Find vi in Vm Find vj in Vt(m) Put in to a list Lt

Compute in O(logn) γk >γm Vm-1 Vt(m-1) Find vi in Vm-1\Vm γk ≦γm Find vj in Vt(m-1)\ Vt(m) Put in to a list Lt

Maintain the list Lt Arranged in nonincreasing order with respect to the first coordinate of its elements Eliminating dominated points

Maintain the list Lt If there are n’ insertions into, and n” deletions from the list Lt during a step , The respective effort is O( n’logn’ + n”)

Find the optimal path Given the planar superset WL, we can then identify N DO(PL) in O(|WL|log|WL|) When the set N DO(PL) is given and ordered according to the MAX coordinates, we can generate the extreme points of its convex hull in O(n) time.

O(nlogn) for following problems, The doubly weighted path α-centdian problem min{MAX(P) + αSUM(P): P∈PL} The doubly weighted, center α-restricted path median problem min{SUM(P) : P∈PL, MAX(P) ≦α} The doubly weighted, median α-restricted path center problem min{MAX(P) : P∈PL, SUM(P) ≦α}

Open problems Minimize the variance of the nodes from the path Minimize the sum of the k lorgest weighted distances from the selected facility Can we solve min{MAX(P) : P∈PL, SUM(P) ≦α} in O(n) Can we solve min{SUM(P), MAX(P) ≦α} in O(n)

Thank you for paying attention