A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree Network

Abstract

In a model of facility location problem, the uncertainty in the weight of a vertex is represented by an interval of weights, and the objective is to minimize the maximum “regret.” The most efficient algorithm previously known for finding the minmax regret 1-median in a tree network with nonnegative vertex weights takes O(nlogn) time. We improve it to O(n), settling the open problem posed by Brodal et al. (Oper. Res. Lett. 36:14–18, 2008).

1 Introduction

1.1 The Problem

Deciding where to locate facilities to minimize the communication or transportation costs is known as the facility location problem. For a recent review of this subject, the reader is referred to [10]. The cost function is formulated as the sum of the distances from the nearest facility weighted by the weights of the vertices. In the minmax regret version of this problem, there is uncertainty in the weights of the vertices and/or edge lengths, and only their ranges are known [8, 12, 13]. Chen and Lin (Theorem 1 in [8]) proved that in solving this problem, the edge lengths can be set to their maximum values. Therefore, we assume that the (positive) edge lengths are fixed and uncertainty is only in the vertex weights. A particular realization (assignment of a weight to each vertex) is called a scenario. Intuitively, the minmax regret 1-median problem can be understood as a 2-person game as follows. The first player picks a location x to place a facility. The opponent’s move is to pick a scenario s. The payoff to the second player is the cost of x minus the cost of the median, both under s, and he wants to pick the scenario s that maximizes his payoff. Our objective (as the first player) is to select x that minimizes this payoff in the worst case, i.e., over all scenarios.

1.2 Previous Work

The problem of finding the minmax regret 1-median on a network, and a tree network in particular, has been attracting great research interest in recent years, and many researchers have worked on this problem. Kouvelis et al. formulated the problem of finding the minmax regret 1-median on a tree and proposed an O(n ⁴) solution, where n is the number of vertices [13]. Chen and Lin improved it to O(n ³) [8]. Averbakh and Berman then found a simple O(n ²) algorithm [1] and improved it later to O(nlog² n) [2]. Yu et al. [16] proposed an O(nlogn) implementation of the algorithm in [2]. More recently, Brodal et al. also came up with a simpler O(nlogn) algorithm [5]. When the vertices can have negative weights, Burkard and Dollani gave an O(n ²) algorithm [6]. Recently, we improved it to O(nlog² n) [4]. This paper is a full version of our extended abstract presented at COCOON 2012 [3].

In this paper, we present an O(n) time algorithm for trees when the edge lengths are fixed, and each vertex has a weight from an interval of nonnegative values. This settles the open problem posed in [5]. In their O(nlogn)-time algorithms, Yu et al. [16] and Brodal et al. [5] successively reduce the size of the part of the tree in which the optimal location lies. Even though these algorithms reduce this size geometrically, they need to spend O(n) time in each round. The main contribution of this paper is to reduce this time to the order of the size of the remaining part of the tree in each round, which reduces the overall time requirement to O(n). To achieve this, we resort to a few somewhat elaborate algorithms. Our pruning algorithm was inspired by a method used by Megiddo [14].

1.3 Paper Organization

The rest of this paper is organized as follows. In the next section, we first review definitions and some known facts, and then prove a lemma (Lemma 4), which restricts the set of scenarios we need to consider. Section 3 describes methods for computing the medians for the scenarios of interest, and for computing their costs. Section 4 is devoted to the detailed discussion of our main algorithm and its time complexity analysis. Finally, Section 5 concludes the paper.

2 Preliminaries

2.1 Definitions

Let T=(V,E) be a tree network (or simply a tree) with n vertices. We also use T to denote the set of all points (vertices and points on edges) on T. Each vertex v∈V is associated with an interval of nonnegative integer weights $W (v) = [\underline{w}_{v}, \overline{w}_{v}]$, where $0 \leq \underline{w}_{v} \leq \overline{w}_{v}$, and each edge e∈E is associated with a positive length (or distance). In order to exclude a trivial case, we assume $\underline{w}_{v} > 0$ for at least one vertex. For any two points a,b∈T, d(a,b) denotes the shortest distance between a and b on T. If a and/or b is on an edge, then the distance is a prorated fraction of its length. Let $\mathcal{S}$ denote the Cartesian product of all W(v),v∈V:

$${\mathcal{S}} \triangleq \prod_{v\in V} [ \underline{w}_v,\overline{w}_v]. $$

Under a scenario $s \in {\mathcal{S}}$, we define the cost of a point x∈T by

$$ F^s(x) \triangleq \sum_{v\in V} d(v,x) w_v^s, $$

(1)

where $w_{v}^{s}$ denotes the weight of v under s. A location x that minimizes (1) is a 1-median under s. Throughout this paper we use 1-median and median synonymously. We call

$$ R^s (x) \triangleq F^s(x) - F^s \bigl(m(s) \bigr) $$

(2)

the regret [13] of point x under s, where m(s) denotes a median under s. A scenario s is said to dominate another scenario s′ at x if R ^s(x)≥R ^s′(x) holds. We finally define the maximum regret, R ^∗(x), of x as the regret of the scenario that dominates all others at x.

$$ R^*(x) \triangleq \max_{s\in {\mathcal{S}}} R^s (x). $$

(3)

Note that R ^∗(x) is the maximum payoff with respect to x that we mentioned in the Introduction. We seek location x ^∗∈T, called the minmax regret median, that minimizes R ^∗(x). We sometimes refer to x ^∗ as the optimal location. Let $s = \hat{s}(x)$ maximize (2) for a given x∈T. We call $\hat{s}(x)$ and $m(\hat{s}(x))$ a worst case scenario and a worst case alternative for x, respectively [1].

2.2 Properties of Median and Minmax Regret Median in a Tree

Let v∈V be a vertex with degree d connected to vertices v ₁,v ₂,…,v _d . If we remove v and all edges incident to it from T, then d subtrees, T(v ₁),T(v ₂),…,T(v _d ) result. Let W(T(v _i )) denote the total weight of the vertices in T(v _i ). Vertex v is said to be a weight centroid or w-centroid [11] if

$$ W \bigl(T(v_i) \bigr) \leq W(T)/2, $$

(4)

holds for all i=1,2,…,d, where W(T) denotes the total weight of the vertices in T.

Lemma 1

[9]

If the vertex weights are non-negative, a vertex is a median if and only if it is a w-centroid, and there is always a vertex that is a median.

By Lemma 1 we shall assume that a median is always at a vertex. However, the minmax regret median may not be at a vertex [13]. If there exists a vertex u that is a median under all the scenarios, then clearly u is the minmax regret location. In such a case, the problem instance is said to be degenerate.

Lemma 2

In a general graph, we have R ^∗(x ^∗)=0 if and only if the problem instance is degenerate.

Proof

The if part is obvious. So suppose that R ^∗(x ^∗)=0. This implies that under any scenario s we have R ^s(x ^∗)=F ^s(x ^∗)−F ^s(m(s))=0, and thus x ^∗ is a median under s, i.e., the problem instance is degenerate. □

In the rest of the paper, we shall assume that a given problem instance is not degenerate.

Lemma 3

[8, Theorem 1(a)]

Given any point x∈T, there exists a worst-case scenario $\hat{s}(x)$ such that $w_{v}^{\hat{s}(x)} = \underline{w}_{v}$ for any vertex v satisfying $d(x,v) < d(m(\hat{s}(x)),v)$, and $w_{v}^{\hat{s}(x)} = \overline{w}_{v}$ for any vertex v satisfying $d(x,v) > d(m(\hat{s}(x)),v)$. If $d(x,v) = d(m(\hat{s}(x)),v)$, then $w_{v}^{\hat{s}(x)}$ may take any value in $[\underline{w}_{v},\overline{w}_{v}]$.

Let e=(v,v′)∈E, and let T(v) (resp. T(v′)) denote the maximal subtree of T that does not contain e but contains v (resp. v′). Let $s \in {\mathcal{S}}$ be such that $w_{u}^{s} = \overline{w}_{u}$ for each vertex u∈T(v), and $w_{u}^{s} = \underline{w}_{u}$ for each u∈T(v′). Such a scenario s is called a bipartite scenario, and v is the front of s, denoted by f(s). Let ${\mathcal{S}}^{*} \subset {\mathcal{S}}$ be the set of all bipartite scenarios. Under a scenario $s \in {\mathcal{S}}^{*}$, we call the component, each vertex of which has the max (resp. min) weight, the max-weighted component (resp. min-weighted component) and denote it by max(s) (resp. min(s)). By definition, under any scenario $s\in {\mathcal{S}}^{*}$ both max(s) and min(s) are nonempty. Clearly, each vertex v is the front of d(v) scenarios in ${\mathcal{S}}^{*}$, where d(v) denotes the degree of v. Note that scenario $\hat{s}(x)$ in Lemma 3 can be made bipartite. Therefore, we have [1]

$$ \forall x \in T: R^*(x) =\max_{s\in {\mathcal{S}}^*} R^s (x). $$

(5)

Averbakh et al. [1] remark that (5) holds for any network (tree or not).

Let $\tilde{\mathcal{S}} \subset {\mathcal{S}}^{*}$ be the set of scenarios under which a median is in the max-weighted component. The following lemma follows directly from Lemma 3.

Lemma 4

• (a)
  $$ \forall x \in T: R^*(x) =\max_{s\in \tilde{\mathcal{S}}} R^s (x). $$

  (6)

• (b) For any point x∈T, there is a worst case scenario $\hat{s}(x) \in \tilde{\mathcal{S}}$ such that x is not in its max-weighted component.

By Lemma 4(a), we only consider the scenarios in $\tilde{\mathcal{S}}$ in the rest of this paper. Lemma 4(b) will be utilized in our pruning algorithm in Sect. 4.3. A major obstacle, however, is the fact that computing $\{m(s) \mid s \in \tilde{\mathcal{S}}\}$ takes Ω(nlogn) time (Theorem 6.1 in [7]). Much effort will be made to overcome this problem by computing only the medians of relevant scenarios.

3 Medians and Their Costs

Equation (6) implies that, in order to find the optimal location, we need to compare the regrets under the scenarios in $\tilde{\mathcal{S}}$. Since regret is defined by (2), our first task is to compute the medians of different scenarios in $\tilde{\mathcal{S}}$, especially the dominating ones. Given a tree T, we pick an arbitrary vertex r ₀ as its root. Let T(v) denote the subtree of T rooted at v. The subtree of T defined by the vertices that do not belong to T(v) is called the complement of T(v) and is denoted by T ^c(v). For a non-root vertex v, we use p(v) to denote the parent of v.

3.1 Computing Median m(s) for all $s \in \tilde{\mathcal{S}}$ with max(s)=T(v)

Goldman computes a median of a tree under a scenario in linear time [9]. Here, for all v∈V, we compute the medians under every scenario $s \in \tilde{\mathcal{S}}$ such that max(s)=T(v) in linear time. For convenience, we define two arrays for subtree weights, $\overline{W}_{t}[\cdot]$ and $\underline{W}_{t}[\cdot]$, and two arrays for complement weights, $\overline{W}_{c}[\cdot]$ and $\underline{W}_{c}[\cdot]$, as follows.

$$\begin{aligned} &\overline{W}_t[v] = \sum_{u\in T(v)\cap V} \overline{w}_u,\quad\quad \underline{W}_t[v]= \sum _{u\in T(v)\cap V} \underline{w}_u, \\ &\overline{W}_c[v] = \sum_{u\in T^c(v)\cap V} \overline{w}_u,\quad\quad \underline{W}_c[v] = \sum _{u\in T^c(v)\cap V} \underline{w}_u. \end{aligned}$$

We can easily compute $\overline{W}_{t}[\cdot]$ and $\underline{W}_{t}[\cdot]$ in O(n) time. Once they have been computed, to compute $\overline{W}_{c}[v]$, for example, we can use the relation $\overline{W}_{c}[v] = \overline{W}_{t}[r_{0}] - \overline{W}_{t}[v]$. For two points a,b∈T, let π(a,b) denote the shortest path between a and b. Let m(s) denote the median vertex under scenario s that is the farthest from the root of T. The following lemma is implied by a result in [9].

Lemma 5

Given a scenario $s\in \tilde{\mathcal{S}}$, let vertex v be defined by T(v)=max(s). For each vertex u on π(m(s),v), $\overline{W}_{t}[u]$ is at least half the total vertex weight under s.

Proof

Clearly, it suffices to prove the assertion for the case u=m(s). Since m(s) is a median under s, by Lemma 1 we have

$$\overline{W}_t[v]+ \underline{W}_c[v] - \overline{W}_t \bigl[m(s) \bigr] \leq \bigl(\overline{W}_t[v] + \underline{W}_c[v] \bigr)/2, $$

where $\overline{W}_{t}[v] + \underline{W}_{c}[v]$ is the total weight under s, and the left hand side is the weight of T ^c(m(s)) under s. From the above inequality, it follows that

$$\overline{W}_t \bigl[m(s) \bigr] \geq \bigl(\overline{W}_t[v] + \underline{W}_c[v] \bigr)/2. $$

 □

Let us now address the issue of computing $\{m(s) \mid s \in \tilde{\mathcal{S}} \mbox{~and~} r_{0} \notin \max(s)\}$ efficiently. We perform a post-order depth first traversal, carrying out the w-centroid test (4) on each vertex visited. When we visit vertex v during the traversal, we compute m(s) for scenario s with max(s)=T(v), if m(s)∈T(v) (i.e., $s \in \tilde{\mathcal{S}}$). See Fig. 1, where v ₁,v ₂,…,v _k are the child vertices of v. If $\underline{W}_{c}[v]> \overline{W}_{t}[v]$ then m(s)∉T(v) (i.e., $s \notin \tilde{\mathcal{S}}$) by Lemma 1. So assume $\underline{W}_{c}[v] \leq \overline{W}_{t}[v]$. For j=1,2,…,k let s _j be the scenario such that max(s _j )=T(v _j ), and assume also that m(s _j ), such that m(s _j )∈T(v _j ) (i.e., $s_{j} \in \tilde{\mathcal{S}}$), has already been computed. If m(s _j )∉T(v _j ) (i.e., $s_{j} \notin \tilde{\mathcal{S}}$) for all j, then we have m(s)=v, because m(s _j )∉T(v _j ) implies m(s)∉T(v _j ). Let us now assume that there is an index j with m(s _j )∈T(v _j ) (i.e., $s_{j} \in \tilde{\mathcal{S}}$). Lemma 5 implies that m(s) lies either in subtree T(v _j ) with the largest $\overline{W}_{t}[v_{j}]$ or at v.

Fig. 1

max(s)=T(v) for scenario s

Lemma 6

Let s be a scenario such that max(s)=T(v) for a vertex v that has v _j as a child vertex. If there is a median under s that lies in subtree T(v _j ), then there is a median under s that lies on π(m(s _j ),v _j ).

Proof

Suppose that there is a median under s that lies in subtree T(v _j ). Then, by Lemma 5 we have

$$\begin{aligned} \overline{W}_t[v_j] \geq& \bigl\{ \overline{W}_t[v] + \underline{W}_c[v] \bigr\} /2. \end{aligned}$$

(7)

Since the weight of any vertex in T(v) under s is not smaller than that under s _j , m(s _j ) must also lie in T(v _j ). However, m(s) cannot lie in T(m(s _j )), except possibly at m(s _j ). We clearly have

$$\begin{aligned} \forall u \in \pi \bigl(m(s_j),v_j \bigr) : \overline{W}_t[u] \geq& \bigl\{ \overline{W}_t[v_j] + \underline{W}_c[v_j] \bigr\} /2. \end{aligned}$$

(8)

From (7) and (8), it follows that

$$\begin{aligned} \exists u \in \pi \bigl(m(s_j),v_j \bigr) : \overline{W}_t[u] \geq& \bigl\{ \overline{W}_t[v] + \underline{W}_c[v] \bigr\} /2, \end{aligned}$$

(9)

and we have m(s)=u, where u (∈π(m(s _j ),v _j )) is the vertex closest to m(v _j ) satisfying (9). □

Theorem 1

For all v∈V, the medians $\{m(s) \mid s \in \tilde{\mathcal{S}} \wedge \max(s) = T(v)\}$ can be computed in O(n) time.

Proof

By Lemma 5, m(s _j ) lies in subtree T(v _j ) with the largest $\overline{W}_{t}[v_{j}]$ if $s_{j} \in \tilde{\mathcal{S}}$, and by Lemma 6, m(s) lies on π(m(s _j ),v) if $s \in \tilde{\mathcal{S}}$. To identify the vertex m(s), starting from m(s _j ), we test each vertex on π(m(s _j ),v) until the condition of Lemma 1 is satisfied. We perform a post-order traversal of T with some additional steps. When v is visited in the post-order traversal, we compute the maximum weight of its subtrees. A vertex u may be visited for the second time if it is on π(m(s _j ),v), where v _j is a child of v, when v is visited. We charge this time to v, unless the median under s with f(s)=v moves up from m(s _j ), in which case we charge it to m(s _j ). Thus the total time required is O(n). □

3.2 Computing Median m(s) for Some $s \in \tilde{\mathcal{S}}$ with min(s)=T(v)

Let s ^c(v) denote the scenario such that min(s ^c(v))=T(v). As commented earlier, computing $\{m(s) \mid s \in \tilde{\mathcal{S}}\}$ takes Ω(nlogn) time [7]. Fortunately, as we will show, we will need m(s ^c(v)) for only some vertices v. For simplicity, we assume that T is a binary tree. If not, we can easily convert it into one by introducing O(n) dummy vertices of weight 0 [15]. Let v _a (resp. v _b ) denote the left (resp. right) child of root r ₀ of T. It is easy to prove

Lemma 7

Assume that $s^{c}(v_{a}) \in \tilde{\mathcal{S}}$. For any vertex v∈T(v _a ), if m(s ^c(v))∉T(v _a ), then m(s ^c(v))∈π(m(s ^c(v _a )),r ₀).

Let s _T denote the scenario such that max(s _T )=T. Without loss of generality we assume that m(s _T )∈T(v _a ). Under s _T , we define the spine of T as a path 〈r ₀,v ₁=v _a ,v ₂,…,v _z 〉, where v _z is a leaf vertex, through T(v _a )∪{r ₀} as follows. For i=1,…,z−1, let $v'_{i}$ be the child vertex of v _i that is not on the spine. See Fig. 2. Under s _T , the weight of T(v _i+1) is not smaller than that of $T(v'_{i})$.

Fig. 2

Positions of v _g =m _z+1, v _h , and $m(s^{c}(v'_{h}))$

Lemma 8

Let 〈r ₀,v ₁,v ₂,…,v _z 〉 be the spine of T. The medians {m _i ∣i=1,…,z+1} can be computed in O(n) time, where m _i =m(s ^c(v _i )) for i=1,…,z and m _z+1=m(s _T ).

Proof

Under one specific scenario such as s ^c(v _a ), we can find m(s ^c(v _a ))=m ₁ in O(n) time. Assume that m ₁∈T(v _b )∪{r ₀} and let k be the largest index such that m _k lies on π(m ₁,r ₀). (Lemma 7.) Based on Lemma 6, we can find all the medians m ₂,…,m _k that lie on π(m ₁,r ₀) in O(n) time, performing the w-centroid test (4) on the vertices on π(m ₁,r ₀) under s ^c(v _i ) for i=1,…,k. If k<z, then m _k+1,…,m _z lie in T(v _a ). Let us now find them as well as m _z+1. From the definition of the spine π(r ₀,v _z ), it is easy to see that m _z+1 lies on π(r ₀,v _z ). If we collapse T(v _b ) into a “super-vertex” with the weight equal to the total weight of the vertices in it, and consider v _z as the root of the new tree, we have a situation as in Theorem 1, except that only the medians under the scenarios s such that f(s)∈π(m _k+1,v _z ) and r ₀∈max(s) need be computed. Therefore, it can easily be done in O(n) time. □

Suppose we have computed {m _i ∣i=1,…,z+1} by Lemma 8, and let m _z+1=v _g . See Fig. 2. For subtrees $T(v'_{g}), T(v'_{g+1}), \ldots, T(v'_{z-1})$, compare the differences $\overline{W}_{t}[v'_{i}] - \underline{W}_{t}[v'_{i}]$ (g≤i≤z−1), and let $T(v'_{h})$ have the largest difference $\overline{W}_{t}[v'_{h}] - \underline{W}_{t}[v'_{h}]$. Restarting at r ₀, and following the subtrees with the largest weights under $s^{c}(v'_{h})$, we can find $m(s^{c}(v'_{h}))$ in O(n) time. In Fig. 2, it is shown to lie in $T(v'_{j})$.

Lemma 9

• (a) For any $v \in T(v'_{i})$, where 1≤i<g, m(s ^c(v)) lies on π(m _z+1,v _z ) (see the dashed path in Fig. 2).

• (b) For any $v \in T(v'_{i})$, where g≤i≤z, m(s ^c(v)) lies on $\pi(m(s^{c}(v'_{h})),m_{z+1})$ (see the chained path in Fig. 2).

Proof

Let v be any vertex in $T(v'_{i})$. See Fig. 2. The only difference between s _T and s ^c(v) is the weight of T(v). Clearly, T(v) is not heavier under s ^c(v) than under s _T .

(a) [1≤i<g] As v moves towards the spine, T(v) grows, T under s ^c(v) becomes lighter, and m(s ^c(v)) may shift from m _z+1, but will stay on the spine.

(b) [g≤i≤z] As v moves from $v'_{i}$ towards a leaf of $T(v'_{i})$, the weight of T ^c(v) increases. Thus the median will move towards m _z+1. To show that the median moves along $\pi(m(s^{c}(v'_{h})),m_{z+1})$, let us compare the processes of finding $m(s^{c}(v'_{h}))$ and m(s ^c(v)), starting at r ₀. (We don’t actually need to do this to find m(s ^c(v)). There is a more efficient way.) Up to vertex v _j , we follow the same path under $s^{c}(v'_{h})$ and s ^c(v). At v _j , T(v _j+1) may be heavier than $T(v'_{j})$ under s ^c(v), in which case m(s ^c(v))∈π(v _j ,m _z+1). So assume that $T(v'_{j})$ is heavier than T(v _j+1) under s ^c(v) as well. In this case, we enter $T(v'_{j})$ under both scenarios. Whenever we visit the next vertex u in $T(v'_{j})$, the only difference between s ^c(v) and $s^{c}(v'_{h})$ is the weight of T ^c(u), and the weights of the subtrees of u are the same. Thus the same path is taken under the two scenarios. The only difference is that m(s ^c(v)) may be found before $m(s^{c}(v'_{h}))$. □

Let us now actually find m(s ^c(v)) in Case (a) of Lemma 9. Recall that m _z+1=m(s _T ). Under scenario s ^c(v), all the vertices in T(v) take their minimum weights, making T(v) lighter than under s _T . This may put m(s ^c(v)) away from m _z+1=v _g towards v _z . Starting from v _g along π(v _g ,v _z ), we can test each vertex against the condition in (4) to find m(s ^c(v)).

What we actually need later is to find m(s) for all $s \in \tilde{\mathcal{S}}$ with min(s)=T(u) for some vertex u. In other words, we want to compute m(s ^c(v)) for each v such that T(u) is a subtree of T(v). If u is on the spine, Lemma 8 provides the solution. So, let $u \in T(v'_{i})$ as in Fig. 3(a). Imagine that v moves from u towards $v'_{i}$ along $\pi(u,v'_{i})$. As we observed in the previous paragraph, m(s ^c(v)) may move from m _z+1=v _g towards v _z .

Fig. 3

Computing m(s ^c(v)) for $v \in T(v'_{i})$: (a) 1≤i<g; (b) g≤i≤z

To find m(s ^c(v)) for $v \in \pi(u,v'_{i})$ systematically in an efficient way, we construct an array D[0:t], where t=z−g, as follows. For j=0,1,…,z−g, we set D[j] to the minimum amount of weight reduction from s _T in T ^c(v _g ) that causes the median to move to v _g+j . Note that as v moves towards $v'_{i}$ along $\pi(u,v'_{i})$, the weight of T ^c(v _g ) gets reduced. Clearly, the elements of D[⋅] are in the increasing order. It is easy to prove

Lemma 10

Let D[0:t] be as defined above. For a vertex $v \in \pi(u,v'_{i})$, let d be the index satisfying

$$D[d] \leq \overline{W}_t[v] - \underline{W}_t[v] < D[d + 1]. $$

Then m(s ^c(v)) is the dth vertex from v _g on π(v _g ,v _z ).

In Case (b) of Lemma 9, we can find m(s ^c(v)) by a similar method, referring to Fig. 3(b). In this case array D[⋅] is constructed for the vertices on $\pi(m(s^{c}(v'_{h})),m_{z+1})$. Before ending this subsection, we state a simple fact as a lemma.

Lemma 11

Let tree T be rooted at vertex r ₀. For any vertex u∈T, each scenario in $\{s \in \tilde{\mathcal{S}} \mid u \in \min(s)\}$ is either of the following two kinds.

• (a) max(s)=T(v) for some vertex v∉π(u,r ₀).

• (b) s=s ^c(v), where v∈π(u,r ₀).

Note that the medians under all the scenarios of the kind (a) are covered by Theorem 1, while the medians under some of the scenarios of the kind (b) are covered by Lemma 8. We will compute the medians of some of the remaining scenarios later, as we need them.

3.3 Computing Costs of Medians

We first define the subtree costs (with subscript t) and complement costs (with subscript c) relative to the root r as follows:

$$\begin{aligned} &\overline{C}_t[v] = \sum_{u\in T(v)} d(u,v) \overline{w}_u,\quad\quad \underline{C}_t[v]= \sum _{u\in T(v)} d(u,v)\underline{w}_u, \\ &\overline{C}_c[v] = \sum_{u\in T^c(v)} d(u,v) \overline{w}_u,\quad\quad \underline{C}_c[v] = \sum _{u\in T^c(v)} d(u,v)\underline{w}_u. \end{aligned}$$

Arrays $\overline{C}_{t}[\cdot]$, $\underline{C}_{t}[\cdot]$, $\overline{C}_{c}[\cdot]$, and $\underline{C}_{c}[\cdot]$ can be computed in O(n) time. (See Sect. 2.3 of [6].)

Lemma 12

Given the median m(s) under a scenario $s \in \tilde{\mathcal{S}}$, we can compute its cost F ^s(m(s)) in constant time.

Proof

Case (a) (m(s) and f(s) belong to the same subtree under the root r ₀, as in Fig. 4(a)): We can compute m(s) for all such $s \in \tilde{\mathcal{S}}$ in O(n) time by Theorem 1. We now compute their costs F ^s(m(s)) in two possible cases. In Fig. 4, vertex v with weight $\overline{w}_{v}$ (resp. $\underline{w}_{v}$) is indicated by a + (resp. −). Let us consider cost contributions to F ^s(m(s)) from different parts of tree T.

• 1. From T(m(s)): $\overline{C}_{t}[m(s)]$.

• 2. From T(f(s))∖T(m(s)): $\overline{C}_{c}[m(s)] -\{\overline{C}_{c}[f(s)] + d(f(s),m(s))\overline{W}_{c}[f(s)]\}$.

• 3. From T ^c(f(s)): $\underline{C}_{c}[f(s)] + d(f(s),m(s))\underline{W}_{c}[f(s)]$.

It is clear that, using arrays $\overline{C}_{*}[\cdot]$, $\underline{C}_{*}[\cdot]$, $\overline{W}_{c}[\cdot]$, and $\underline{W}_{c}[\cdot]$, where ∗∈{t,c}, we can compute the above three in constant time.

Fig. 4

Illustration for the proof of Lemma 12: (a) Case (a); (b) Case (b)

Case (b) (m(s) and f(s) do not belong to the same subtree under the root r ₀, as in Fig. 4(b)): We can similarly compute F ^s(m(s)) in constant time. □

4 Optimal Facility Location

Now that we have efficient methods to compute medians and their costs, we shall address the main problem of finding the optimal facility location. We first describe our general approach, then present our algorithm, and finally analyze its complexity.

4.1 Prune and Search

Scenario s is said to be dominated in a subtree, if for every point x in the subtree, there is a scenario that dominates s at x. Given a tree T, as in [5, 16], we successively identify smaller and smaller part of T, named T ^∗, that contains the optimal location x ^∗. In addition, we maintain a shrinking set S, initialized to $\tilde{\mathcal{S}}$, of scenarios that may not be dominated in T ^∗, while those in $\tilde{\mathcal{S}} \setminus S$ are known to be dominated. The main issue is that the fronts of the scenarios in S and their medians may belong to T∖T ^∗. To keep track of all the scenarios in S, we maintain a tree T′=(N,E′), called the auxiliary tree, which contains T ^∗ in it. See Fig. 5.

Fig. 5

Auxiliary tree T′ containing T ^∗. The hollow circles represent dummy nodes

The node set¹ N of T′ consists mainly of the front vertices of the scenarios in S. We define the scenario-weight of a node u∈T′ to be the number of scenarios in S that have u as their fronts. A node with scenario-weight 0 is called a dummy node, and it does not represent the front node of any scenario in S. Each node in T′∖T ^∗ will have a scenario-weight of no more than one, after every scenario s such that max(s)⊃T ^∗ has been discarded. (Note that they are dominated in T ^∗ by Lemma 3.) After that, if a scenario whose front u is in T′∖T ^∗ is discarded, then u becomes a dummy node. If this is a leaf node, we simply remove it from T′, together with the incident edge. If a node u with degree 2 becomes dummy, we remove u and connect its neighbors u′ and u″ with an edge of length d(u,u′)+d(u,u″). As a result, every leaf node is non-dummy, and there is no dummy node with degree 2. For example, see Fig. 5, where the hollow circles indicate the dummy nodes. Therefore, the number of dummy nodes cannot be more than the number of leaves. This implies that the number of nodes in T′ is O(|S|).

If we remove a point y∈T and the edges incident to it from T, a number of “subtrees” result. Any such “subtree” with point y and the edge to it restored is called a y-branch [2] of T. We use B _T (y,x) to denote the y-branch of T that contains point x (≠y). We now cite a useful lemma.

Lemma 13

[2, Lemma 1]

For any point x∈T, the optimal location x ^∗ is in the x-branch in which the worst case alternative $m(\hat{s}(x))$ for x lies, where $s = \hat{s}(x)$ maximizes R ^s(x).

To localize x ^∗ eventually to a point, we want to make the sizes of T ^∗ and S smaller and smaller. To this end, we pick the pivot vertex r∈T ^∗, determine the r-branch of T ^∗ that contains the optimal location x ^∗, and update T ^∗ to this r-branch. We want to choose r judiciously, so that the sizes of new T ^∗ and S will be no more than a constant fraction of their current sizes. With these considerations, we use a w-centroid of T′ (based on the scenario-weights) as r, which can be found in time linear in the size of T ^∗ [9]. By definition of the w-centroid, none of the r-branches minus r, T ^∗∖{r} in particular, contains more than |S|/2 fronts, and therefore, T′∖T ^∗∪{r} contains at least |S|/2 fronts. This fact will be used in deriving (18) later.

After picking pivot vertex r, theoretically, we can determine B _T′(r,x ^∗) of T′, based on Lemma 13. The practical difficulty is that we need some medians that are not covered by Theorem 1 or Lemma 8. For those other medians, we need to resort to Lemma 10, but we cannot afford to spend more than O(|S|) time in total, which is a challenge that we will overcome later.

4.2 Preparation

Let us define S _min(r) by

$$\begin{aligned} S_{\min}(r) = \bigl\{ s \in S \mid \min(s) \supseteq B_{T'} \bigl(r,x^* \bigr) \setminus \{r\} \bigr\} . \end{aligned}$$

(10)

Lemma 14

[16]

Let s∈S _min(r). Then the cost function F ^s(x) over x∈T ^∗∩B _T′(r,x ^∗) has the following properties:

• (a) It is a non-decreasing linear function of point x on each edge, as x moves away from r.

• (b) It is continuous at the vertices.

Lemma 15

Let s,s′∈S _min(r). Unless R ^s(x)=R ^s′(x) for all x∈T ^∗, R ^s(x)=R ^s′(x) holds for at most one point x∈π(r,u) for each leaf u of T ^∗.

Proof

Let e=(v,v′) be an edge of T ^∗ such that v′ is closer to r than v is. The rates of change of F ^s(x) and F ^s′(x) (hence of R ^s(x) and R ^s′(x)) with respect to x∈e, as x moves towards v′ are (W ^s−W ^s(v))−W ^s(v)=W ^s−2W ^s(v) and W ^s′−2W ^s′(v), respectively, where W ^s(v) is the total weight under s of the subtree T(v), and W ^s is the total weight under s of all the vertices of T. Their difference is thus

$$\begin{aligned} \bigl\{ W^s - W^{s'} \bigr\} + 2 \bigl\{ W^{s'}(v) -W^s(v) \bigr\} . \end{aligned}$$

(11)

The term {W ^s−W ^s′} clearly does not depend on the edge e on which x lies. Clearly, {W ^s′(v)−W ^s(v)}=0 holds, because s,s′∈S _min(r). Therefore, R ^s(x)=R ^s′(x) holds for at most one point x∈π(r,u), unless R ^s(x)=R ^s′(x) for all x∈T ^∗. □

Lemma 16

Assume that $\overline{W}_{*}[\cdot]$, $\underline{W}_{*}[\cdot]$, $\overline{C}_{*}[\cdot]$, and $\underline{C}_{*}[\cdot]$ are known, where ∗∈{t,c}. Given a set $S \subset \tilde{S}$ of scenarios and a point x such that (i) ∀s∈S:x∈min(s), and (ii) {m(s)∣s∈S} are known, we can determine in O(|S|) time the scenario $\hat{s}(x) \in S$ that dominates all others in S at x, and the x-branch that contains $m(\hat{s}(x))$, i.e., $B_{T^{*}}(x,m(\hat{s}(x)))$.

Proof

We need to compute R ^s(x)=F ^s(x)−F ^s(m(s)) for each s∈S. We can compute F ^s(m(s)) in O(1) time by Lemma 12. To evaluate F ^s(x), we interchange the max-weighted vertices and min-weighted vertices (f(s) moves as a result) in Fig. 4, and replace m(s) by x, except that x can be any point, not necessarily a vertex. Following the method in the proof Lemma 12, it is clear that F ^s(x), hence R ^s(x), can be computed for all s∈S in O(|S|) time. Then $\hat{s}(x)$ is given by the scenario s that maximizes R ^s(x). It is easy to find $B_{T^{*}}(x,m(\hat{s}(x)))$. □

Regarding Condition (i) in Lemma 16, if x∉min(s) for s∈S then s is dominated by some other scenario at x, and can be ignored. Condition (ii) assumes the medians {m(s)∣s∈S} are available, but computing them is still a pending issue to be settled in the next section.

4.3 Algorithm

We first introduce a procedure that performs the task of Lemma 16, which runs in O(|S|) time.

Procedure OptBranch(S,x): [{m(s)∣s∈S∧x∈min(s)} are known]

Find the x-branch that contains the optimal location.

We start with $S = \tilde{\mathcal{S}}$ and the initial pivot r set to the w-centroid of T′, and keep track of the shrinking scenario set S and T ^∗ that is an r-branch containing the optimal location x ^∗. To find this r-branch, we need to know the medians of the scenarios in {s∈S∣r∈min(s)}. Then we can remove from S the scenarios that are dominated in T ^∗. The scenarios in {s∈S∣max(s)⊇T ^∗} are obviously dominated in T ^∗ and can be discarded. Among the remaining scenarios in S, we pay special attention to those in {s∈S∣min(s)⊇T ^∗}.

We use the w-centroid of T as r ₀. Assume that the medians of the scenarios covered by Theorem 1 have been computed, so that the medians of the scenarios in $\{s \in \tilde{S} \mid r_{0} \in \min(s)\}$ are known. We also assume that the medians {m _i ∣i=1,…,z+1} have been computed by Lemma 8. Here is an outline of our algorithm, where κ is a constant.

Algorithm Prune

• 1. Set T ^∗=T and $S = \tilde{\mathcal{S}}$.

• 2. For j=1,2,… , carry out Steps 3 to 7.

• 3. Pick a pivot vertex r. If r is not on the spine, compute the medians of the scenarios $\{s^{c}(v) \in S \mid v \in \pi(r,v'_{i})\}$, where $r \in T(v'_{i})$ in Fig. 2.

• 4. Invoke Procedure OptBranch(S,r) to determine the r-branch that contains the optimal location x ^∗. Update T ^∗ to this r-branch.

• 5. Discard from S the scenarios in {s∈S∣max(s)⊇T ^∗}.

• 6. Let S _min(r) (⊆S) be the set of scenarios defined by (10). Pair up scenarios in S _min(r), and let p be the number of pairs.²

• 7. Determine and discard at least ⌈p/4⌉ dominated scenarios from S. If |S|≤κ, then locate x ^∗ by an exhaustive means or by applying any of the algorithms currently available (e.g., that in [2]) and stop.

The first thing we do in a round is to pick pivot r in Step 3. As we discuss later, in general, we set the pivot r to the w-centroid of T ^∗. Thus in Step 3 of the first round, we have r=r ₀. To determine the r-branch of T ^∗ that contains the optimal location x ^∗, $B_{T^{*}}(r,x^{*})$ in Step 4, we may need some preparation in Step 3, by computing the needed medians {m(s)∣s∈S∧r∈min(s)}. See Lemmas 10 and 11. But in the first round they are already known.

Since Step 5 is straightforward, let us now discuss Steps 6 and 7, which form the core of Algorithm Prune. Since {m(s)∣s∈S∧r∈min(s)} are available after Step 3, then obviously {m(s)∣s∈S _min(r)}, which is needed in Step 6, are also available, except possibly for one scenario.³ Step 7 requires, among others, computing the cross-over point of the regret functions R ^s(x) and R ^s′(x) of each pair (s,s′) of scenarios constructed in Step 6. Note that m(s) and m(s′) were either precomputed or computed in Step 3. The most favorable cases are where either R ^s(x)=R ^s′(x) for all x∈T ^∗ or R ^s(x) and R ^s′(x) don’t cross each other in T ^∗. In these cases, one of s and s′ is dominated by the other in T ^∗ and can be thrown away, achieving a 2-to-1 reduction. However, in the worst case, there may be no such pair.

Let us assume the least favorable case, where R ^s(x)=R ^s′(x) has a (non-zero) finite number of solution points in T ^∗. See Lemma 15. All solution points to R ^s(x)=R ^s′(x) lie at the same distance from r. Suppose that d ₁,d ₂,…,d _p are the distances from r of the solution points for the p pairs of scenarios. Let d _m be the ⌈p/2⌉th smallest among them, and let d ^∗ denote the distance from r of the optimal location x ^∗, which is not known yet. If d ^∗≥d _m (resp. d ^∗<d _m ), then from each scenario pair with solution point distance d _i ≤d _m (resp d _i ≥d _m ), one of them can be thrown away, because the other dominates it at any point x that is not nearer (resp. nearer) than d _m from r.

We now show how to determine if d ^∗≥d _m for a given value d _m  (>0) without knowing the exact value of d ^∗. Let y ₁,y ₂,…,y _c be the points in T ^∗ at distance d _m from r. For example, see y ₁,…,y ₅ in Fig. 6. Let $\overline{T}(y_{i})$ be the y _i -branch that is “below” (farther away from r) y _i . Thus $\overline{T}(y_{i}) = T(y_{i})$ holds if y _i is a vertex. Let S _i (⊂S) denote the set of scenarios such that for any s∈S _i we have $\max(s) \cap T^{*} \subseteq \overline{T}(y_{i})$. Thus their min-weighted components contain r. Define

$$ \overline{R}(y_i) = \max_{s\in S_i} \bigl\{ F^s(y_i) - F^s \bigl(m(s) \bigr) \bigr\} , $$

(12)

and let s _i ∈S _i realize $\overline{R}(y_{i})$. Note that we already know {m(s)∣s∈S _i } as a result of Step 3. So we can determine s _i in O(|S _i |) time by Lemma 16. Among them let $\overline{R}(y_{k})$ (realized by s _k ∈S _k ) be as large as any other. We now compute R ^∗(y _k ) and $\hat{s}(y_{k})$ based on the scenarios in $S~(\subset\tilde{\mathcal{S}})$, which is the set of all scenarios in $\tilde{\mathcal{S}}$ that have not been thrown away so far. This can be done in O(|S|) time by Lemma 16, provided the relevant medians are known. The relevant medians that we don’t know yet are those under the scenarios whose min-weighted (resp. max-weighted) components contain y _k (resp. r). If such a median is not known yet, we can resort to Lemma 10 with u=y _k .

Fig. 6

Points y ₁,y ₂,…,y ₅ are at distance d _m from r

Lemma 17

For a given value d _m of x, define {y _i ∣i=1,2,…,c} and y _k as above.

• (a) If $\hat{s}(y_{k}) \in S_{k}$ then the optimal location x ^∗ lies in $\overline{T}(y_{k})$.

• (b) If $\hat{s}(y_{k}) \notin S_{k}$ then the optimal location x ^∗ cannot lie in $\overline{T}(y_{i})$ for any i.

Proof

(a) Follows from Lemma 13, since $\hat{s}(y_{k}) \in \tilde{S}$, hence $m(\hat{s}(y_{k})) \in \overline{T}(y_{k})$.

(b) The assertion is trivially true for i=k. Assume that the optimal location (over S) was in $\overline{T}(y_{j})$ (j≠k). Then by Lemmas 4 and 13, the scenario that realizes R ^∗(y _j ) must be in S _j , and hence $R^{*}(y_{j}) = \overline{R}(y_{j})$. By the definition of k, we have

$$ R^*(y_j) = \overline{R}(y_j) \leq \overline{R}(y_k). $$

(13)

On the other hand, we have

$$ \overline{R}(y_k) < R^{s_k}(y_j), $$

(14)

by Lemma 14. We have strict inequality here, because y _j is farther away from median m(s _k ) than y _k . By definition, we also have

$$ R^{s_k}(y_j) \leq R^*(y_j). $$

(15)

Equations (13), (14) and (15) yield R ^∗(y _j )<R ^∗(y _j ), a contradiction. □

Procedure OptBranch(S,y _k ) can determine whether we have Case (a) or (b) of Lemma 17. In Case (a), we can eliminate one scenario from each pair of scenarios, s and s′, whose crossover point (where R ^s(x) and R ^s′(x) intersect) is at most distance d _m away from r. In Case (b), we can eliminate one scenario from each pair of scenarios whose crossover point is at least distance d _m away from r. Note that to execute Procedure OptBranch(S,y _k ), we need the medians of the scenarios $\{s^{c}(v) \in S \mid v \in \pi(v_{k},v'_{i})\}$, which can be computed by Lemma 10. However, computing them individually takes too much time. In the next subsection, we present a way to batch them to save time.

4.4 Two-Phase Tree Search

Assume that a target sequence of ordered data points is given as an array, D[0:t], where D[0]=0, and D[i]<D[i+1] holds for i=1,…,t−1. There are also q arrays, Q _j [1:l _j ] of integers (j=1,…,q), Q _j [i]≤Q _j [i+1] holds for 1≤i<l _j , and $\sum_{j=1}^{q} l_{j} \leq n$. Our objective is to assign Q _j [k] to D[h] such that D[h]≤Q _j [k]<D[h+1] for k=1,2,…,l _j . A naïve approach might merge Q _j [⋅] and D[⋅] into one ordered sequence for each j, which takes

$$\begin{aligned} O \Biggl(\sum_{j=1}^q \{l_j + t\} \Biggr) = O \Biggl(qt + \sum _{j=1}^q l_j \Biggr) = O(qt+n) \end{aligned}$$

(16)

time. Lemma 18 will show that with one-time preprocessing, which takes O(t) time, it can be done in

$$\begin{aligned} O \Biggl(\sum_{j=1}^q \bigl\{ l_j\log (t/l_j) +l_j \bigr\} \Biggr) +O(t) \end{aligned}$$

(17)

time. At first glance, (17) may not appear any better than (16), but if l _i ≤cnα ⁱ, where c and α are constants satisfying c>0 and 0<α<1, then (17) becomes O(n), as proved in Theorem 2.

In preprocessing, we construct a balanced binary tree τ _D on t leaves representing D[0],D[1],…,D[t], from left to right. Given a query array Q _j [⋅] of ascending integers, we want to assign Q _j [k] to D[h] such that D[h]≤Q _j [k]<D[h+1]. During the construction of τ _D , we label each internal node⁴ u by d[u], which is the value of the leftmost leaf of the subtree rooted at u. Tree τ _D can be constructed in O(t) time. Let τ _D (u) denote the subtree of τ _D rooted at u.

Algorithm 2PTS(D[0:t],Q[1:l])

• Phase 1: If ⌈logl⌉>⌊logt⌋,⁵ then for k=1,2,…,l find h _k such that D[h _k ]≤Q[k]<D[h _k +1] by merging two ordered arrays D[⋅] and Q[⋅], and stop. Otherwise, let l′=2^⌈logl⌉. Identify all the nodes, u ₁,u ₂,…,u _l′, of τ _D that are at level (=depth) ⌈logl⌉. For k=1,2,…,l find i such that d[u _i ]≤Q[k]<d[u _i+1], by merging the sequence 〈d[u ₁],d[u ₂],…,d[u _l′]〉 and the elements in the ordered array Q[⋅].

• Phase 2: For each k=1,2,…,l, move down in τ _D (u _i ) to reach the leaf node D[h _k ] such that D[h _k ]≤Q[k]<D[h _k +1].

Lemma 18

Algorithm 2PTS(D[0:t],Q[1:l]) runs in O(llog(t/l)+l) time.

Proof

It is clear that 2PTS(D[0:t],Q[1:l]) runs in O(l) time if ⌈logl⌉>⌊logt⌋. So, assume ⌈logl⌉≤⌊logt⌋. In Phase 1, we test Q[k] against the value stored at successive u _i without backtracking. This takes O(l+l′)=O(l) time, and each element Q[k] has been assigned to a node at level ⌈logl⌉. In Phase 2, the length of a path from level ⌈logl⌉ down to a leaf is at most ⌈logt⌉−⌈logl⌉=O(log(t/l)). For all the l elements in Q[⋅], the total time is thus O(llog(t/l)). □

4.5 Time Complexity Analysis

To make our analysis easier, we start with ${\mathcal{S}}^{*}$ instead of $\tilde{\mathcal{S}}$. Let us first consider Round 1, in which we have just found a w-centroid r ₀ in the auxiliary tree T′=T and identified T ^∗. For each leaf u of T there is just one scenario in ${\mathcal{S}}^{*}$, whose max-weighted component consists of just u. Let γ be the total number of scenarios in ${\mathcal{S}}^{*}$ whose min-weighted components contain T ^∗, and let δ be the total number of scenarios in ${\mathcal{S}}^{*}$ whose max-weighted components contain T ^∗ (hence r). Note that for each node v, there are d(v) scenarios in ${\mathcal{S}}^{*}$ whose fronts are on v, where d(v) denotes the degree of v. For node v in T∖T ^∗, among those d(v) scenarios, all but one contain T ^∗ (hence r) in their max-weighted components. At any point x∈T ^∗, these d(v)−1 scenarios are dominated by other scenarios by Lemma 3. Since T ^∗ keeps shrinking over the successive rounds, this dominance relation does not change in the future, which implies that we can throw them away for good.

The total number of scenarios in ${\mathcal{S}}^{*}$ whose fronts are on the nodes in T∖T ^∗∪{r ₀} is given by

$$\begin{aligned} \gamma+\delta +1 \geq& |S|/2, \end{aligned}$$

(18)

where the inequality holds because r ₀ is a w-centroid. On the left hand side of (18), “+1” accounts for the scenario s with min(s)=T ^∗∖{r}. Step 4 (resp. Step 7) of Algorithm Prune throws away δ (resp. γ/8) scenarios from S. We have

$$\begin{aligned} \delta + \gamma/8 =& (7/8)\delta +(\gamma+\delta+1)/8 -1/8 \\ =& (7\delta-1)/8 +(\gamma+\delta+1)/8 \\ \geq& |S|/16, \end{aligned}$$

(19)

since δ>1. Therefore, Algorithm Prune removes at least |S|/16 scenarios, reducing the size of S by at least 1/16 in each round. Thus, after round j, the size of S reduces to less than 2n(15/16)^j. Note that $|{\mathcal{S}}^{*}| = 2(n - 1)$, because each edge of T gives rise to two scenarios in ${\mathcal{S}}^{*}$.

Assume that the medians of the scenarios covered by Theorem 1 and the medians {m _i ∣i=1,…,z+1} have been computed by Lemma 8. To execute OptBranch(S,r) (resp. OptBranch(S,y _k )) invoked in Step 4 (resp. Step 7) of Algorithm Prune, we need some other medians. We first discuss the medians needed to execute OptBranch(S,r). If r lies on the spine, then we already know the medians of all scenarios in {s∈S∣r∈min(s)}. So, let $u = r \in T(v'_{i})$ in Fig. 3. We will only discuss how to find the medians covered by Lemma 9(a), since those covered by Lemma 9(b) can be computed similarly. For this purpose, we introduced Algorithm 2PTS(D[0:t],Q[1:l]) in Sect. 4.4. To use it, we need the target sequence D[0:t] associated with the vertices on π(m _z+1,v _z ), which we constructed just before Lemma 10. We then construct a search tree τ _D , which is introduced in Sect. 4.4.

As for the query array Q[1:l], let v be the jth vertex (counting from r) along $\pi(r,v'_{i})$ in the set $\{v \in \pi(r,v'_{i}) \mid s^{c}(v) \in S\}$. We set $Q[j] = \overline{W}_{t}[v] - \underline{W}_{t}[v]$. (See Lemma 10.) Clearly, the elements of Q[⋅] are in the non-decreasing order. We can now execute Algorithm 2PTS(D[0:t],Q[1:l]), to locate $\{m(s^{c}(v)) \mid v \in \pi(r,v'_{i}) \wedge s^{c}(v) \in S\}$.

The medians needed for OptBranch(S,y _k ) can be computed similarly, considering path $\pi(y_{k},v'_{i})$ instead of $\pi(r,v'_{i})$.⁶ The S-size of a path π is defined to be the number of vertices in {v∈π∣s ^c(v)∈S}. We now prove an important theorem.

Theorem 2

Let π ₁,π ₂,…,π _q be disjoint paths in T(v _a ) of S-sizes, l ₁,l ₂,…,l _q , respectively, such that for each j, π _j is a subpath of a path that starts at r ₀. Under the conditions that l _j ≤cnα ^j for each j, where c and α are constants satisfying c>0 and 0<α<1, and n is the size of tree T, we can find m(s ^c(v)) for all vertices v∈π _j for all j in O(n) time.

Proof

In Phase 1 of Algorithm 2PTS(D[0:t],Q[1:l _j ]), we can use level ⌈cnα ^j⌉ of τ _D in Phase 1. Then by Lemma 18, the medians under the scenarios in {s ^c(v)∈S∣v∈π _j } can be computed in O(l _j log(t/⌈cnα ^j⌉)) time after some preprocessing (construction of D[0:t] and τ _D ) that costs O(t) time. Thus the total time required by Algorithm 2PTS() to compute m(s ^c(v)) for all j and for all vertices v∈π _j is given by

$$\begin{aligned} & O \Biggl(\sum_{j=1}^q l_j\log \bigl(t/ \bigl\lceil c n\alpha^j \bigr\rceil \bigr) +l_j \Biggr) \\ &\quad\leq O \Biggl(\sum_{j=1}^q \bigl(c \alpha^j n \bigr) \log \bigl(\alpha^{-j} /c \bigr) \Biggr) +O(n) \\ &\quad= O \Biggl(nc\log (1/\alpha) \sum_{j=1}^q j\alpha^j - nc\log c \sum_{j=1}^q \alpha^j \Biggr) +O(n) \\ &\quad= O(n), \end{aligned}$$

(20)

since t<n and $\sum_{j=1}^{q} j\alpha^{j}< \alpha/(1-\alpha)^{2}$ holds independently of q, if 0<α<1. □

In applying Theorem 2, we set $\pi_{j} = \pi(r,v'_{i})$ for the jth round of Algorithm Prune. Here we define l _j as the S-size of π _j . The paths, such as $\pi(r,v'_{i})$, satisfy the condition of Theorem 2 with l _j ≤cn(15/16)^j, since l _j <|S|≤cn(15/16)^j.

Let |S|=k and let t(k) be the time needed for the repeated executions of Algorithm Prune to find the optimal location, starting with the scenarios in S. Since the execution of Algorithm Prune once takes linear time, the recurrence relation on t(k) is

$$ t(k) \leq t(15k/16) + O(k). $$

(21)

This recurrence equation has the solution of the form t(k)=O(k). Once k becomes smaller than some constant, we can solve the problem exhaustively. We thus have the main result of this paper:

Theorem 3

The minmax regret 1-median of a tree can be found in O(n) time, where n is the number of vertices in the given tree.

5 Conclusion and Future Work

We have presented an O(n) time algorithm for computing the minmax regret 1-median for trees with nonnegative vertex weights. This improves upon the previously known best complexity of O(nlogn), and is the best possible. Our next goal is to design an algorithm for a cactus network. A more challenging problem is how to compute the minmax regret p-median for various families of networks. We believe that some techniques that we have developed in this paper will be useful in solving other facility location and minmax problems.