Minmax Regret k-Sink Location on a Dynamic Path Network with Uniform Capacities

Abstract

In Dynamic flow networks an edge’s capacity is the amount of flow (items) that can enter it in unit time. All flow must be moved to sinks and congestion occurs if flow has to wait at a vertex for other flow to leave. In the uniform capacity variant all edges have the same capacity. The minmax k-sink location problem is to place k sinks minimizing the maximum time before all items initially on vertices can be evacuated to a sink. The minmax regret version introduces uncertainty into the input; the amount at each source is now only specified to within a range. The problem is to find a universal solution (placement of k sinks) whose regret (difference from optimal for a given input) is minimized over all inputs consistent with the given range restrictions. The previous best algorithms for the minmax regret version of the k-sink location problem on a path with uniform capacities ran in O(n) time for $k=1$, $O(n \log ^ 4 n)$ time for $k=2$ and ${\varOmega }(n^{k+1})$ for $k >2$. A major bottleneck to improving those solutions was that minmax regret seemed an inherently global property. This paper derives new combinatorial insights that allow decomposition into local problems. This permits designing two new algorithms. The first runs in $O(n^3 \log n)$ time independent of k and the second in $O( n k^2 \log ^{k+1} n)$ time. These improve all previous algorithms for $k >1$ and, for $k > 2$, are the first polynomial time algorithms known.

1 Introduction

Dynamic flow networks model movement of items on a graph. The process starts with each vertex v assigned some initial set of supplies $w_v$. Supplies flow between neighboring vertices. Each edge e has a given capacity $c_e$ which limits the rate of the flow of supplies entering that edge in unit time. If there is some $c >0$ such that $\forall e,\, c_e \equiv c$, the network has uniform capacity. Each e also has associated with it a time required to traverse e. Note that as supplies move around the graph, congestion can occur, as supplies back up at a vertex.

Dynamic flow networks were introduced by Ford and Fulkerson in [18] and have since been extensively researched. One well studied problem on such networks is transshipment, e.g., [23], in which the graph has several sources and sinks, with supplies on the sources and each sink having a specified demand. The problem is to find the quickest time required to satisfy all of the demands. Hoppe and Tardos [23] provide a polynomial time algorithm for this problem.

Dynamic Flow also models evacuation problems [21]. Vertices model buildings and the items on vertices represent evacuees in buildings. Since our work also fits this evacuation analogy, we will refer to items on vertices as evacuees. and edges are roads connecting buildings. The sinks play the role of exits to safety from the roads. The problem is to find a routing strategy (evacuation plan) that evacuates everyone to the sinks in minimum time. In these problems the evacuation plan is vertex based. That is, all supplies from a vertex evacuate out through a single edge given by the plan (corresponding to a sign at that vertex stating “this way out”). Such a flow, in which all flow through a vertex leaves through the same edge, is known as confluent. The basic minmax optimization problem is to determine a plan that minimizes the total time needed to evacuate all the evacuees. Confluent flows are known to be difficult on general graphs; solving, or even approximating to a constant factor, the quickest confluent flow problem with even one sink is NP-Hard [19, 24]. Research on finding exact quickest confluent dynamic flows is therefore restricted to special graphs, such as trees and paths.

In some versions of the problem the sinks are known in advance. In others, such as the one addressed in this paper, locating the sinks that minimize the evacuation time is part of the problem; only the numberk of allowed sinks is given as input. Mamada [28] gives an $O(n \log ^2 n)$ algorithm for solving the 1-sink problem on a dynamic tree network. Higashikawa et al. [21] improve this down to to $O(n \log n)$ for uniform capacities. For k sinks this can be solved in $O(n k^2 \log ^5 n)$ time for general capacities and $O(n k^2 \log ^4 n)$ for uniform capacities [15]. Higashikawa et al. [22] show how to solve the k-sink problem on a uniform capacity dynamic path network in O(kn) time which was later reduced down to $O\left( \min ( n \log n, n + k^2 \log ^2 n)\right)$ by [7]. We note that all the results above refer to the minmax problem of minimizing the maximum evacuation time. There is also a corresponding minsum problem of minimizing the total sum of all of the evacuation times of all of the flow. This can be solved on a dynamic path network [5] in time $O(k n^2 \log ^2 n)$ for general capacities and $O(k n \log ^3 n)$ for uniform capacities.

In practice, the exact number of evacuees located at a vertex is unknown at the time the plan is drawn up and robust optimization is needed. One approach to robust optimization is probabilistic, with the number of evacuees at a vertex being drawn from known distributions. In another, the one used in this paper, all that is known is the (interval) range in which that number may fall. One way to deal with this type of uncertainty is to find a plan that minimizes the regret, e.g. the maximum discrepancy between the evacuation time for the given plan on a fixed input and the plan that would give the minimum evacuation time for that particular input. This is known as the minmax regret problem. Minmax regret optimization has been extensively studied for k-median [10, 13, 38] and k-center [3, 11, 32, 38] ([12] is a recent example) along with many other optimization problems [17, 33, 37]. Aissi et al. [1], Averbakh and Lebedev [4], Candia-Véjar et al. [14] and Kouvelis and Gang [25] provide an introduction to the literature. Since most of these problems are NP-Hard to solve exactly on general graphs, the vast majority of the literature is again concerned with algorithms on special graphs, in particular paths and trees.

Recently there has been a series of new results for k-sink evacuation on special structure dynamic graphs. The 1-sink minmax regret problem on a uniform capacity path was originally proposed by [16] who gave an $O(n \log ^2 n)$ algorithm. This was reduced down to $O(n \log n)$ by [20, 34, 35] and then to O(n) by [9]. Xu and Li solve the 1-sink minmax regret problem on a uniform capacity cycle in $O(n^3 \log n)$ time [36]. Higashikawa et al. [21] provides an $O(n \log ^2 n)$ algorithm for the 1-sink minmax regret problem on a uniform capacity tree; this was reduced to $O(n \log n)$ by [9].

Returning to the minmax regret problem uniform capacity path case; for $k=2$, [27] gave an $O(n^3 \log n)$ algorithm, later reduced to $O(n \log ^4 n)$ by [9].

For $k >2$ the only previous algorithm known was $O\left( n^{1+k} (\log n)^{1 + \log k}\right)$ [30]. The exponential growth with k for that algorithm was an inherent property of the structural technique used.

We also note two other related sink regret problems. The first is the regret version of the $k=1$ minsum problem on a path with uniform capacities. This was originally solved in $O(n^3)$ time by [5] and then reduced down to $O(n^2 \log ^2 n)$ time by [8]. The second is the original minmax regret problem with $k=1$ sink on a general graph with uniform capacities and confluent flows but with the problem restricted so that every vertex evacuates all of its flow along the shortest path to the sink. This can be solved [26] in $O(m^2 n^3)$ time where m is the number of edges in the graph.

Organization This paper develops new structural properties of the minmax regret solution for paths, leading to better algorithms. Section 3 proves that, independent of k, there are only $O(n^2)$ worst case scenarios that need to checked. This independence permits overcoming the exponential dependence upon k in [30]. Section 4 develops properties of worst-case solutions that could lead to efficient algorithms. Section 5 develops further such properties. Section 6 develops two such algorithms, both of which improve on the previous ones in all $k>1$ cases. The first, better for small k, runs in $O(n k^2 (\log n)^{k+1 })$, which will be the best algorithm for any fixed $k >1$. In particular for $k=2$, it runs in $O(n \log ^3 n)$ time improving upon the $O(n \log ^4 n)$ algorithm of [9]. The second, which is better for large k (where k is dependent upon n) runs in $O(n^3 \log n)$ time with no dependence upon k. Section 7 discusses possible extensions. We emphasize that this paper assumes that all edges have the same capacity. This follows all prior work in this area e.g., on the path [9, 16, 20, 34, 35], trees [9, 21] and the cycle [36], which make the same uniform capacity assumption. Section 7 briefly discusses the structural reason why this and all previous work have not attempted to address the case in which different edges can have different capacities.

Finally, we note that our algorithms use as a subroutines procedures for efficiently calculating evacuation times. These procedures are straightforward modifications of well-developed techniques from [7, 9, 16] and contain very few new ideas. To keep this paper self contained, their proofs are provided in the “Appendix” in Sect. 8.

2 Preliminary Definitions

2.1 Model Definition

Let $P=(V,E)$ be a path of $(n+1)$ vertices $V=\{x_{0},x_{1},\ldots ,x_{n}\}$ along a line: $x_0< x_1< \ldots < x_n$. $E=\{e_{1},e_{2},\ldots ,e_{n}\}$ with $e_{i}=(x_{i-1},x_{i})$ are the n edges connecting the $x_i$. For intuition we will sometimes refer to the vertices as buildings and the edges as roads connecting the buildings. Flow will correspond to evacuees.

We use $d(x_i,x_j) = |x_{i}-x_{j}|$ to denote the distance between $x_{i}$ and $x_{j}$ and $\tau$ to denote its paceor inverse-speed. Thus, travelling from $x_i$ to $x_j$ requires $\tau d(x_i,x_j)$ time. All edges have fixed capacity$c>0$; this is the number of items that can enter an edge in unit time. Intuitively, this can be visualized as the road’s width (number of lanes), i.e., the number of items that can travel in parallel along the road.

Each vertex $x_i$ also has a fixed but unknown weight $w_i \ge 0$ denoting the number of people (evacuees) initially located at $x_i$. The input is a range$[w_{i}^{-},w_{i}^{+}]$ within which $w_i$ must lie.

Let ${\mathcal {S}}$ denote the Cartesian product of all weight intervals for $0\le i\le n$:

$$\begin{aligned} {\mathcal {S}} \,{:=}\, \prod _{0\le i\le n}[w_{i}^{-},w_{i}^{+}]. \end{aligned}$$

A scenario$s\in {\mathcal {S}}$ is an assignment of weights to all vertices. The weight of a vertex$x_{i}$under scenarios is denoted by $w_{i}(s)$. ${\mathcal {S}}$ is the set of all scenarios consistent with the input restrictions.

Our arguments will often use “${{\,\mathrm{arg\,max}\,}}$”. In the case of ties, “${{\,\mathrm{arg\,max}\,}}$” returns the smallest index that achieves the maximum, i.e.,

$$\begin{aligned} \mathop {\mathrm{arg\,max}}\limits _{ i \in {{{\mathcal {I}}}}} f(i) \,{:=}\, \min \left\{ j\in {{\mathcal {I}}} \,:\, f(j) = \max _{i \in {{\mathcal {I}}}} f(i)\right\} . \end{aligned}$$

2.2 Evacuation Time

Let $P=(V,E)$ be a path with uniform edge capacity c, pace $\tau$ and specified scenario $s\in \mathcal {S}$.

Fig. 1

Illustration of left and right evacuation. Scenario s assigns $w_j = w_j(s)$ initial units of flow to vertex $x_j$. All verices are evacuated to a sink at x. The time ${\varTheta }_L(P,x,s)$ to evacuate everything to the left of x to x and the time ${\varTheta }_R(P,x,s)$ to evacuate everything to the right of x to x are given by Eqs. 1 and 2. Total evacuation time is the maximum of the two

2.2.1 Left and Right Evacuation

Consider W units of flow starting at vertex $x_{i}$ moving right. They require $W/c + \tau (x_{i+1} - x_{i})$ time until the last flow arrives at $x_{i+1};$W / c time before the last flow leaves $x_{i}$ and $\tau (x_{i+1} - x_{i})$ further time until it arrives at $x_{i+1}$. If this flow is continuing on to $x_{i+2}$, it might or might not have to wait at $x_{i+1}$ before entering edge $[x_{i+1},x_{i+2}]$, depending upon whether other evacuees remain present on $x_{i+1}$ at the time the first flow from $x_{i}$ arrives there. It is these congestion effects that complicate the analysis.

Consider a single sink $x\in P$ (x is not restricted to be a vertex in V).

See Fig. 1. Define ${\varTheta }_L(P,x,s)$ (resp. ${\varTheta }_R(P,x,s)$) to be the time taken to evacuate everything to the left (right) of sink x to x under scenario s. The left (right) evacuation times have been derived by many authors, e.g., [9] to be

$$\begin{aligned} {\varTheta }_{L}(P,x,s)= & {} \max _{x_i < x\,:\, W^s_{0,i}> 0} \left\{ (x-x_{i})\tau +\frac{W^s_{0,i}}{c} \right\} \end{aligned}$$

(1)

$$\begin{aligned} {\varTheta }_{R}(P,x,s)= & {} \max _{x_i> x\,:\, W^s_{i,n}> 0} \left\{ (x_{i}-x)\tau + \frac{W^s_{i,n}}{c} \right\} \end{aligned}$$

(2)

where for $a \le b$, $W^s_{a,b} = \sum _{j=a}^b w_j(s)$.

Note Intuitively, ${\varTheta }_{L}(P,x,s)$ is the time at which the last evacuee from $x_0$ arrives at x. Let $x_{i}<x$ be any vertex. The time required for the first evacuee leaving $x_{i}$ to travel to x, without congestion, is $T_1(i) =\tau (x-x_{i})$. The minimum time required for all evacuees in $[x_0,x_{i}]$ to pass through $x_{i}$ is $T_2(i) = \frac{1}{c} W^s_{0,i}$. Thus ${\varTheta }_{L}(P,x,s) \le T_1(i) + T_2(i)$. This is valid for every i so the right side of Eq. 1 is a lower bound for ${\varTheta }_{L}(P,x,s)$. One can show that if $x_{i^*}$ is the rightmost vertex at which the first evacuee from $x_0$ experiences congestion by having to wait, then ${\varTheta }_{L}(P,x,s) = T_1(i^*) + T_2(i^*)$, proving (1). The derivation of ${\varTheta }_{R}(P,x,s)$ is similar.

As stated, our setup assumes that sinks may be placed anywhere on the path and not just on a vertex. We note that our results will continue to hold even if sinks are restricted to be on vertices, i.e., our algorithms will still find the minmax regret k-sink location problem in the same amount of time under those new placement restrictions. Section 7 briefly discusses why this is true.

2.2.2 1-Sink Evacuation

The evacuation time to sinkx is the maximum of the left and right evacuation times: (Fig. 1)

$$\begin{aligned} {\varTheta }^1(P,x,s) \,{:=}\, \max \Bigl \{ {\varTheta }_{L}(P,x,s),{\varTheta }_{R}(P,x,s)\Bigr \}. \end{aligned}$$

(3)

Fig. 2

k-sink evacuation on Path P with partitions and sinks $\{{\hat{P}}, {\hat{Y}}\}$

2.2.3 k-Sink Evacuation

Definition 1

(Fig. 2) A separation of path P into k subpaths is denoted by ${\hat{P}}=\{P_1,P_2,\ldots ,P_k\}$, $P_i = [x_{l_i}, x_{r_i}]$ where $l_1 =0$, $r_k=n$ and $l_{i+1} = r_i +1$. Each $P_i \in {\hat{P}}$ will be called a partition. ${\hat{Y}} =\{y_1,y_2,\ldots ,y_k\}$ denotes a set of sinks such that $y_i\in P_i$. Given ${\hat{P}}$ and sinks ${\hat{Y}}$, vertices in partition $P_i$ are restricted to evacuate only to sink $y_i$

Every vertex belongs to only one subpath. This implies that all evacuees passing through the same vertex must evacuate to the same sink, i.e., a confluent routing. The pair $\{{\hat{P}},{\hat{Y}}\}$ defines an evacuation protocol for the path P.

The k-sink evacuation time with evacuation protocol$\{{\hat{P}},{\hat{Y}}\}$under scenarios is the maximum of the evacuation times within the individual partitions, i.e.,

$$\begin{aligned} {\varTheta }^k(P,\{{\hat{P}},{\hat{Y}}\},s) \,{:=}\, \max _{1\le i\le k} {\varTheta }^1(P_{i},y_i,s) \end{aligned}$$

(4)

Definition 2

Given ${\hat{P}},{\hat{Y}}$, set

$$\begin{aligned} d \,{:=}\, \mathop {\mathrm{arg\,max}}\limits _{1\le i\le k} {\varTheta }^1(P_{i},y_i,s) . \end{aligned}$$

The partition $P_d$ with maximum evacuation cost (breaking ties to the leftmost) is called the “dominant partition for$\{{\hat{P}},{\hat{Y}}\}$under scenarios”. We use $y_d$ to denote “the sink associated with the dominant partition$P_d$”.

2.3 The Optimal k-Sink Location Problem

The Optimalk-Sink Location Problem is to find the minimum evacuation cost using k sinks, i.e,

$$\begin{aligned} {\varTheta }^k_{\mathrm {opt}}(P,s) \,{:=}\, \min _{{\hat{P}},{\hat{Y}}} {\varTheta }^k\left( P,\{{\hat{P}},{\hat{Y}}\},s\right) , \end{aligned}$$

and an evacuation protocol $\{{\hat{P}}^*,{\hat{Y}}^*\}$ that achieves this minimum, i.e.,

$$\begin{aligned} {\varTheta }^k\left( P,\{{\hat{P}}^*,{\hat{Y}}^*\},s\right) = {\varTheta }^k_{\mathrm {opt}}(P,s). \end{aligned}$$

2.4 Regret

For fixed $\{{\hat{P}},{\hat{Y}}\}$ and $s\in {\mathcal {S}}$, the regret is defined as the difference between ${\varTheta }^k(P,\{{\hat{P}},{\hat{Y}}\},s)$ and the optimal k-sink evacuation time for s, i.e.,

$$\begin{aligned} R\left( \{{\hat{P}},{\hat{Y}}\},s\right) \,{:=}\, {\varTheta }^k(P,\{{\hat{P}},{\hat{Y}}\},s)-{\varTheta }^k_{\mathrm {opt}}(P,s) \end{aligned}$$

(5)

The following self-evident property will be needed later:

Property 1

If $P_d$ is the dominant partition for $\{{\hat{P}},{\hat{Y}}\}$ under scenario s, then

$$\begin{aligned} R\left( \{{\hat{P}},{\hat{Y}}\},s\right) ={\varTheta }^1(P_d,y_d,s) - {\varTheta }^k_{\mathrm {opt}}(P,s) \ge 0. \end{aligned}$$

Definition 3

The maximum regret (called max-regret) achieved (over all scenarios) for a choice of $\{{\hat{P}},{\hat{Y}}\}$ is:

$$\begin{aligned} R_{\max }\left( \{{\hat{P}},{\hat{Y}}\}\right) \,{:=}\, \max _{s\in {\mathcal {S}}}\left\{ R\left( \{{\hat{P}},{\hat{Y}}\},s\right) \right\} \end{aligned}$$

(6)

If $R_{\max }(\{{\hat{P}},{\hat{Y}}\})=R(\{{\hat{P}},{\hat{Y}}\},s^*)$ for some scenario $s^*\in {\mathcal {S}}$, then $s^*$ is a worst-case scenario for $\{{\hat{P}},{\hat{Y}}\}$.

Definition 4

The k-sink minmax regret value for P is

$$\begin{aligned} R_{\max }^k (P) \,{:=}\, \min _{\{{\hat{P}},{\hat{Y}}\}} R_{\max }\left( \{{\hat{P}},{\hat{Y}}\}\right) . \end{aligned}$$

2.5 The Minmax Regret k-Sink Location Problem

The input for the minmax regret k-Sink Location Problem is a dynamic path network with path P, vertex weight intervals$[w_i^-,w_i^+]$, edge capacity c, and pace $\tau$. The problem can be viewed as a 2-person Stackelberg game [31, 97–98] between the algorithm A and adversary B:

• 1. Algorithm A (leader): creates an evacuation protocol $\{{\hat{P}},{\hat{Y}}\}$ as defined in Sect. 2.2.3.

• 2. Adversary B (follower): chooses a regret-maximizing worst-case scenario$s^*\in {\mathcal {S}}$ for $\{{\hat{P}},{\hat{Y}}\}$ i.e., $R(\{{\hat{P}},{\hat{Y}}\},s^*) = R_{\max }(\{{\hat{P}},{\hat{Y}}\})$.

A’s objective is to find $R_{\max }^k (P)$ and an evacuation protocol $\{{\hat{P}}^*,{\hat{Y}}^*\}$ that minimizes this max-regret, i.e.,

$$\begin{aligned} R_{\max }^k (P) = R_{\max }\left( \{\hat{P^*},\hat{Y^*}\}\right) . \end{aligned}$$

3 Worst Case Scenarios and Their Properties

A priori, every $\{{\hat{P}},{\hat{Y}}\}$ might have a different associated worst case scenario. This section describes an $O(n^2)$ size set of scenarios ${\mathcal {S}}^*$ that contains a worst case scenario for every evacuation protocol. That is, for every $\{{\hat{P}},{\hat{Y}}\}$, some $s^* \in {\mathcal {S}}^*$ is a worst-case scenario for $\{{\hat{P}},{\hat{Y}}\}$.

For $k=1$, all the previous work on minmax regret on paths¹ used the existence of an O(n) size set that contains a worst-case scenario for each protocol. The intuitive reason why the algorithm in [30] blew up exponentially in k was that it needed to check an exponentially growing (in k) set of worst case scenarios. The main observation of this paper, the one leading to improved algorithms, is that only a set of size $O(n^2)$, independent ofk, is needed.

To derive ${\mathcal {S}}^*$, start by assuming that A has chosen $\{{\hat{P}},{\hat{Y}}\}$ and B has countered by choosing some worst-case scenario$s^*\in {\mathcal {S}}$ for that $\{{\hat{P}},{\hat{Y}}\}$. Let $P_d\in {\hat{P}}$ be the dominant partition for $\{{\hat{P}},{\hat{Y}}\}$ under $s^*$.

Lemma 1 describes how to modify $s^*$ outside $P_d$; Theorem 1 describes how to modify $s^*$ within $P_d$. Both types of modifications will maintain $s^*$ as being worst case for $\{{\hat{P}},{\hat{Y}}\}$ and $P_d$ as its dominant partition.

Fig. 3

Illustrations of Lemma 1 and Definition 5. “+”s denote that $w_i(s) = w_i^+$. “−”s denote that $w_i(s) = w_i^-$

Lemma 1

See Fig. 3a. Let $s^* \in {\mathcal {S}}$ be a worst-case scenario for $\{{\hat{P}},{\hat{Y}}\}$ with $P_d$ its associated dominant partition. Define $s^*_B$ by

$$\begin{aligned} w_{i}(s^*_B) \,{:=}\, \left\{ \begin{array}{ll} w_{i}(s^*) &{} \quad \text{ if } \,\, x_i \in P_d,\\ w_{i}^{-} &{} \quad \text{ if } \,\, x_i \not \in P_d. \end{array} \right. \end{aligned}$$

Then $s^*_B$ is also a worst-case scenario for $\{{\hat{P}},{\hat{Y}}\}$ with dominant partition $P_d$.

Proof

The evacuation time in $P_d$ is the same for $s_B^*$ as for $s^*$ because $w_i(s^*) = w_i(s_B^*)$ within $P_d$. The evacuation time in the other partitions might be less in $s_B^*$ than $s^*$ since some of the values might be decreased but that can only reduce the evacuation times in other partitions. Thus

$$\begin{aligned} {\varTheta }^k\left( P,\{{\hat{P}},{\hat{Y}}\},s_B^*\right) ={\varTheta }^1(P_d,y_d,s_B^*) ={\varTheta }^1(P_d,y_d,s^*) = {\varTheta }^k(P,\{{\hat{P}},{\hat{Y}}\},s^*)\quad \end{aligned}$$

(7)

where $y_d$ is the sink associated with $P_d$.

Furthermore, reducing the value of some $w_i(s^*)$ can not increase the optimal evacuation time so,

$$\begin{aligned} {\varTheta }_{\mathrm {opt}}^k(P,s_B^*)\le {\varTheta }_{\mathrm {opt}}^k(P,s^*). \end{aligned}$$

(8)

Thus

$$\begin{aligned} R(\{{\hat{P}},{\hat{Y}}\},s^*_B)= & {} {\varTheta }^k(P,\{{\hat{P}}, {\hat{Y}}\},s_B^*) - {\varTheta }^k_{\mathrm {opt}}(P,s^*_B) \\\ge & {} {\varTheta }^k(P,\{{\hat{P}},{\hat{Y}}\},s^*)- {\varTheta }^k_{\mathrm {opt}}(P,s^*) \\= & {} R\left( \{{\hat{P}},{\hat{Y}}\},s^*\right) . \end{aligned}$$

Thus $s_B^*$ is also a worst-case scenario with dominant partition $P_d$. $\square$

Lemma 1 permits assuming that all vertices outside $P_d$ have weights $w_i^-$. We now examine the scenario inside$P_d$.

Definition 5

See Fig. 3b. Consider Partition $P^{\prime }=[x_l,x_r]$. and let $s\in {\mathcal {S}}$ be any fixed scenario.

A scenario $s\in {\mathcal {S}}$ is called left/right-dominant for $P^{\prime }$ if, $w_{j}(s)=w_{j}^{-}$ for $j < l$ and $j >r$ and there exists some i satisfying $l\le i\le r$ such that

• Left-dominant:$w_{j}(s)=w_{j}^{+}$ for $l\le j<i$ and $w_{j}(s)=w_{j}^{-}$ for $i \le j \le r$.

• Right-dominant:$w_{j}(s)=w_{j}^{-}$ for $l\le j<i$ and $w_{j}(s)=w_{j}^{+}$ for $i \le j \le r$.

Given ${\hat{P}}$ and $P_i \in {\hat{P}}$, let ${\mathcal {S}}_L^i$ (resp. ${\mathcal {S}}_R^i$) denote the set of all left-dominant (resp. right-dominant) scenarios for $P_i$.

Theorem 1

Fix $\{{\hat{P}},{\hat{Y}}\}$. Let $s^* \in {\mathcal {S}}$ be any worst-case scenario for $\{{\hat{P}},{\hat{Y}}\}$ and $P_d$ its associated dominant partition. Then there exists a scenario $s_B^* \in {\mathcal {S}}_L^d\bigcup {\mathcal {S}}_R^d$ such that $s^*_B$ is also a worst-case scenario for $\{{\hat{P}},{\hat{Y}}\}$ with $P_d$ its associated dominant partition.

Proof

See Fig. 4. Let $s^*\in {\mathcal {S}}$ be a worst-case scenario for $\{{\hat{P}},{\hat{Y}}\}$ with associated dominant partition $P_d= [x_{l_d},x_{r_d}]\in {\hat{P}}$. Without loss of generality, from Lemma 1, we may assume that for $x_i$ outside $P_d$, $w_i(s^*_B) = w_i^-$.

To prove the Theorem we show that by only changing weights within$P_d$, we can modify $s^*$ to $s_B^* \in {\mathcal {S}}_L^d\bigcup {\mathcal {S}}_R^d$ while regret does not decrease.

Without loss of generality, assume that ${\varTheta }_L(P_d,y_d,s^*) \ge {\varTheta }_R(P_d,y_d,s^*)$ (the other case is symmetric). From Eq. 1,

$$\begin{aligned} {\varTheta }_{L}(P_d,y_d,s^*)=\max _{\begin{array}{c} i \,:\, x_{l_d} \le x_i < y_d \\ W^{s^*}_{l_d,i} >0 \end{array}} g(P_d,y_d,s^*\,:\, i) \end{aligned}$$

(9)

where

$$\begin{aligned} g(P_d,y_d,s^*\,:\, i) = (y_d-x_i)\tau + \frac{1}{c} W^{s^*}_{l_d,i}. \end{aligned}$$

(10)

Let m be the index i which maximizes the right hand side of Eq. 9 (in case of ties, choose the smallest such i).

We now show the transformation from $s^*$ to $s_B^*$. There are three possible locations for vertices $x_t \in P_d$ (see Fig. 4):

Fig. 4

Illustration of proof of Theorem 1. A left-dominantworst-case scenario for $P_d$ with sink $y_d$. Left evacuation time dominates. m is the index i that maximizes Eq. 10

${\hbox {(i)} \, y_d \le x_t \le x_{r_d}:}$ For any such t, set $w_t(s^*_B) = w_t^{-}$. Reducing a weight can not increase evacuation time so

$$\begin{aligned} {\varTheta }_R(P_d, y_d, s^*_B) \le {\varTheta }_R(P_d, y_d, s^*) \le {\varTheta }_L(P_d, y_d, s^*) = {\varTheta }_L(P_d, y_d, s^*_B). \end{aligned}$$

Thus ${\varTheta }^1(P_d, y_d, s^*_B) = {\varTheta }^1(P_d, y_d, s^*)$. By the definition of dominant partition,

$$\begin{aligned} {\varTheta }^k\left( P,\{{\hat{P}},{\hat{Y}}\},s^*_B\right) = {\varTheta }^1(P_d, y_d, s^*_B) = {\varTheta }^1(P_d, y_d, s^*) = {\varTheta }^k(P,\{{\hat{P}},{\hat{Y}}\},s^*). \end{aligned}$$

Finally, reducing weights can only decrease the optimal evacuation time so

$$\begin{aligned} {\varTheta }_{\mathrm {opt}}^k(P,s_B^*) \le {\varTheta }_{\mathrm {opt}}^k(P,s^*) \end{aligned}$$

${\hbox {(ii)} \, x_{m+1} \le x_t < y_d:}$ Again, for such t, set $w_t(s^*_B) = w_t^{-}$. After this transformation, for $i \ge m+1$, $g(P_d,y_d,s^*_B\,:\, i) \le g(P_d,y_d,s^*\,:\, i)$ while for $i < m+1$, $g(P_d,y_d,s^*_B\,:\, i) = g(P_d,y_d,s^*\,:\, i)$ so, by the choice of m,

$$\begin{aligned} {\varTheta }_L(P_d, y_d, s^*) = {\varTheta }_L(P_d, y_d, s^*_B) \end{aligned}$$

and still ${\varTheta }^1(P_d, y_d, s^*_B) = {\varTheta }^1(P_d, y_d, s)$. By the same argument as in (i),

$$\begin{aligned} {\varTheta }^k\left( P,\{{\hat{P}},{\hat{Y}}\},s^*_B\right) ={\varTheta }^k\left( P,\{{\hat{P}},{\hat{Y}}\},s^*\right) . \end{aligned}$$

and

$$\begin{aligned} {\varTheta }_{\mathrm {opt}}^k(P,s_B^*) \le {\varTheta }_{\mathrm {opt}}^k(P,s^*) \end{aligned}$$

${\hbox {(iii)} \, x_{l_d} \le x_t \le x_m:}$ For such t, set $w_t(s_B^*) = w_t^+$. Then, simple calculation yields

$$\begin{aligned} {\varTheta }_L(P_d,y_d,s_B^*) = {\varTheta }_L(P_d,y_d,s^*) + \left( w_t^+ - w_t(s^*)\right) /c \end{aligned}$$

where m remains the index that maximizes the value in Eq. 9. Thus,

$$\begin{aligned} {\varTheta }^1(P_d,y_d,s_B^*) = {\varTheta }_L(P_d,y_d,s_B^*) = {\varTheta }_L(P_d,y_d,s^*) + \left( w_t^+ - w_t(s^*)\right) /c \end{aligned}$$

so, again, by the definition of dominant partition,

$$\begin{aligned} {\varTheta }^k\left( P,\{{\hat{P}},{\hat{Y}}\},s^*_B\right) = {\varTheta }^k(P,\{{\hat{P}},{\hat{Y}}\},s^*) + \left( w_t^+ - w_t(s^*)\right) /c. \end{aligned}$$

Also, increasing any one weight by can only increase the evacuation time by at most the amount of the increase divided by c , so

$$\begin{aligned} {\varTheta }_{\mathrm {opt}}^k(P,s_B^*) \le {\varTheta }_{\mathrm {opt}}^k(P,s^*) + \left( w_t^+ - w_t(s^*)\right) /c \end{aligned}$$

We have thus seen, for t in any of case (i), (ii), (iii),

$$\begin{aligned} R(\{{\hat{P}},{\hat{Y}}\},s^*_B)= & {} {\varTheta }^k\left( P,\{{\hat{P}},{\hat{Y}}\},s^*_B\right) -{\varTheta }^k_{\mathrm {opt}}(P,s^*_B) \\\ge & {} {\varTheta }^k(P,\{{\hat{P}},{\hat{Y}}\},s^*)-{\varTheta }^k_{\mathrm {opt}}(P,s^*) \\= & {} R(\{{\hat{P}},{\hat{Y}}\},s^*). \end{aligned}$$

$s^*$ is a worst case scenario with associated dominant partition $P_d$, so $s^*_B$ must be one as well.

The discussion above considered changing only one $w_t$. Repeating this process for every $t \in [x_{l_d},x_{r_d}]$ yields a left dominant scenario, $s^*_B$ for $P_d$. The case in which the right evacuation time dominates is totally symmetric and creates a right-dominant scenario for $P_d$.

We therefore can always create a worst case scenario in ${\mathcal {S}}_L^d\bigcup {\mathcal {S}}_R^d$. $\square$

Fig. 5

Illustration of Definition 6. Scenario $s_B^*(t_1,t_2)$ has $w_i^+$ entries for $t_1 \le i < t_2$ and $w_i^-$ entries everywhere else

Definition 6

See Fig. 5. For integers $t_1,t_2$ satisfying $0 \le t_1 \le t_2 \le n$ define²$s_B^*(t_1,t_2)$ as satisfying

$$\begin{aligned} w_i(s_B^*(t_1,t_2)) \,{:=}\, {\left\{ \begin{array}{ll} w_{i}^{-} &{} \text{ if } 0\le i<t_{1},\\ w_{i}^{+} &{} \text{ if } t_{1}\le i<t_{2}\\ w_{i}^{-} &{} \text{ if } t_{2}\le i\le n \end{array}\right. } \end{aligned}$$

and set

$$\begin{aligned} \mathcal {S^*} \,{:=}\, \left\{ s_B^*(t_1,t_2) \,:\, t_1,t_2, \text{ such } \text{ that } \, 0 \le t_1 \le t_2 \le n+1\right\} \end{aligned}$$

Note that all scenarios of the type described by Theorem 1 are in $\mathcal {S^*}$. Thus

Property 2

Let $\{{\hat{P}},{\hat{Y}}\}$ be some evacuation protocol. Then there exists $s^*_B \in {\mathcal {S}}^*$ that is a worst-case scenario for $\{{\hat{P}},{\hat{Y}}\}$. Note that $\left| {\mathcal {S}}^* \right| = O(n^2)$.

If the ${{\hat{P}}}$ is known in advance, there is a stronger property.

Definition 7

Consider partition $P_{l r}= [x_l,x_r]$. Set

$$\begin{aligned} \mathcal {S^*}\left( P_{l r}\right) \,{:=}\, \bigcup _{t=l}^{r} \bigl \{ s_B^*(l,t), s_B^*(t,r+1)\bigr \}. \end{aligned}$$

Note that $\mathcal {S^*}\left( P_{l r}\right) \subseteq \mathcal {S^*}$ and $\left| \mathcal {S^*}\left( P_{l r}\right) \right| = O(x_r - x_l +1)$.

Then Theorem 1 directly implies

Property 3

Let ${\hat{P}} = \{P_1,\ldots ,P_k\}$ fix ${\hat{Y}}$ and suppose there exists some worst-case scenario $s^*$ for $\{{\hat{P}},{\hat{Y}}\}$ with associated dominant partition $P_d$. Then there exists a scenario $s^*_B \in \mathcal {S^*}\left( P_d\right)$ that is also a worst case scenario for $\{{\hat{P}},{\hat{Y}}\}$ with dominant partition $P_d$.

Next

Definition 8

For ${\hat{P}} = \{P_1,\ldots ,P_k\}$ set

$$\begin{aligned} \mathcal {S^*}\left( {\hat{P}}\right) \,{:=}\, \bigcup _{1 \le i \le k} S^*(P_i). \end{aligned}$$

Note that $\mathcal {S^*}\left( {\hat{P}}\right) \subseteq \mathcal {S^*}$ and $\left| \mathcal {S^*}\left( {\hat{P}}\right) \right| = \sum _i O(x_r - x_l +1) = O(n)$.

Since some partition must be dominant this yields

Property 4

The set $\mathcal {S^*}\left( {\hat{P}}\right)$ includes some worst case scenario for $\{{\hat{P}},{\hat{Y}}\}$.

4 Local Costs of Partitions

This section uses the properties derived in Sect. 3 to associate local costs with partitions and then show that the minmax regret value is the maximum of these local costs. This will enable designing efficient algorithms.

4.1 Local Partition Costs

Theorem 2

Let $l \le r$, set $P_{l r} = [x_l, x_r]$ and let $s\in {\mathcal {S}}$ be any scenario. Define

$$\begin{aligned} \forall y\in & {} P_{l r},\quad R_{l r}(y,s) \,{:=}\, {\varTheta }^1(P_{l r}, y,s) - {\varTheta }^k_{\mathrm {opt}}(P,s), \end{aligned}$$

(11)

$$\begin{aligned} \forall y\in & {} P_{l r},\quad R_{l r}(y) \,{:=}\, \max _{s\in S^*}\left\{ R_{l r}(y,s)\right\} , \end{aligned}$$

(12)

and

$$\begin{aligned} R_{l r} \,{:=}\, \min _{x_{l} \le y \le x_{r}} R_{l r}(y). \end{aligned}$$

(13)

Then the minmax regret value for P satisfies

$$\begin{aligned} R_{\max }^k (P) = \min _{{\hat{P}}} \max _{1\le i\le k}\left\{ R_{l_i r_i}\right\} \end{aligned}$$

(14)

where we denote ${\hat{P}}$ by ${\hat{P}} = \{P_1,\ldots ,P_k\}$ with $P_i = [x_{l_i},x_{r_i}]$

Proof

The regret associated with $\{{\hat{P}},{\hat{Y}}\}$ under scenario $s\in {\mathcal {S}}$ is

$$\begin{aligned} R\left( \{{\hat{P}},{\hat{Y}}\},s\right)&= {\varTheta }^k(P,\{{\hat{P}},{\hat{Y}}\},s) - {\varTheta }^k_{\mathrm {opt}}(P,s)&(\text {from Eq.}~5) \nonumber \\&= \max _{1\le i\le k}\left\{ {\varTheta }^1(P_i,y_i,s)\right\} - {\varTheta }^k_{\mathrm {opt}}(P,s)&(\text {from Eq.}~2) \nonumber \\&= \max _{1\le i\le k}\left\{ {\varTheta }^1(P_i,y_i,s) - {\varTheta }^k_{\mathrm {opt}}(P,s)\right\}&\nonumber \\&= \max _{1\le i\le k}\left\{ R_{l_i r_i}(y_i,s)\right\} .&\end{aligned}$$

(15)

The maximum in Eq. 15 is achieved when $i=d$, where $P_d$ is the dominant partition.

The max-regret for $\{{\hat{P}},{\hat{Y}}\}$ can be written as:

$$\begin{aligned} R_{\max }(\{{\hat{P}},{\hat{Y}}\})&= \max _{s\in {\mathcal {S}}}\left\{ R(\{{\hat{P}},{\hat{Y}}\},s)\right\}&(\text {from Eq.}~6)\nonumber \\&= \max _{s\in \mathcal {S^*}}\left\{ R(\{{\hat{P}},{\hat{Y}}\},s)\right\}&(\text {from Prop}~2)\nonumber \\&= \max _{s\in S^*}\max _{1\le i\le k}\left\{ R_{l_i r_i}(y_i,s)\right\}&(\text {from Eq.}~15) \nonumber \\&= \max _{1\le i\le k} \max _{s\in {\mathcal {S}}^*}\left\{ R_{l_i r_i}(y_i,s) \right\} \nonumber \\&= \max _{1\le i\le k}\left\{ R_{l_i r_i}(y_i)\right\}&(\text {from Eq.}~12) \end{aligned}$$

(16)

To complete the proof note that the minmax regret value can be written as:

$$\begin{aligned} R_{\max }^k (P)&= \min _{\{{\hat{P}},{\hat{Y}}\}} R_{\max }(\{{\hat{P}},{\hat{Y}}\}) \nonumber \\&= \min _{\{{\hat{P}},{\hat{Y}}\}} \max _{1\le i\le k}\left\{ R_{l_i r_i}(y_i)\right\}&(\text {from Eq.}~16) \nonumber \\&= \min _{{\hat{P}}} \left\{ \min _{1 \le i \le k\, :\, y_i \in P_i} \left\{ \max _{1\le i\le k}\left\{ R_{l_i r_i}(y_i)\right\} \right\} \right\}&\nonumber \\&= \min _{{\hat{P}}} \left\{ \max _{1\le i\le k} \left\{ \min _{1 \le i \le k\, :\, y_i \in P_i}R_{l_i r_i}(y_i)\right\} \right\}&\end{aligned}$$

(17)

$$\begin{aligned}&= \min _{{\hat{P}}} \max _{1\le i\le k}\left\{ R_{l_i r_i}\right\} .&\end{aligned}$$

(18)

$\square$

Table 1 The definitions of $R_{l r}$, ${\bar{R}}_{l r}$ and $R'_{l r}$ and associated d, ${\bar{d}}$ and $d'$ for given ${\hat{P}}$

Theorem 2 alone would permit developing a polynomial time Dynamic Programming algorithm for evaluating $R_{\max }^k (P)$. The remainder of this subsection defines two related quantities $R'_{l r}$ and ${\bar{R}}_{l r}$, that permit developing faster algorithms. These are listed in Table 1 for comparison.

Definition 9

Let $l \le r$. Set

$$\begin{aligned} (\mathrm{a})&\quad&\forall y \in P_{l r},&\quad&R'_{l r}(y)&\,{:=}\, \max _{s\in S^*(P_{ l r})}\left\{ R_{l r}(y,s)\right\} ,&\nonumber \\&&R'_{l r}&\,{:=}\, \min _{x_{l} \le y \le x _{r}} R'_{l r}(y).&\end{aligned}$$

(19)

$$\begin{aligned} (\mathrm{b})&&{\bar{R}}_{l r}&\,{:=}\, \max \{R_{l r},\, 0\}&\end{aligned}$$

(20)

We now prove that Eq. 14 will remain valid if $R_{l r}$ is replaced by $R'_{ l r}$ or ${\bar{R}}_{ l r}$. The final results that will be used for algorithmic development are stated in Lemma 6 and Theorem 3.

Definition 10

Let ${\hat{P}}=\{P_1,P_2,\ldots ,P_k\}$. Set

$$\begin{aligned}&d\left( {\hat{P}}\right) \,{:=}\, \mathop {\mathrm{arg~max}}\limits _{1 \le i \le k} R_{l_i r_i}, \quad \quad d'\left( {\hat{P}}\right) \,{:=}\, \mathop {\mathrm{arg~max}}\limits _{1 \le i \le k} R'_{l r_i}, \\&{\bar{d}}\left( {\hat{P}}\right) \,{:=}\, \mathop {\mathrm{arg~max}}\limits _{1 \le i \le k} {\bar{R}}_{l r_i}. \end{aligned}$$

Lemma 2

Let $d = d\left( {\hat{P}}\right)$ where ${\hat{P}}=\{P_1,P_2,\ldots ,P_k\}$. Then

$$\begin{aligned} R_{l_d r_d} = \max _{1\le i\le k}\left\{ R_{l_i r_i}\right\} \ge 0. \end{aligned}$$

(21)

Proof

From Property 1, regret is always nonnegative, so $R_{\max }^k (P) \ge 0$. Thus, from Theorem 2,

$$\begin{aligned} 0 \le R_{\max }^k (P) = \min _{{\hat{P}}} \max _{1\le i\le k}\left\{ R_{l r_i}\right\} . \end{aligned}$$

In particular, for any fixed ${\hat{P}}$ satisfying $d = d\left( {\hat{P}}\right)$, Eq. 21 holds. $\square$

Lemma 3

$$\begin{aligned} \forall i,\quad {\bar{R}}_{ii} =0 \end{aligned}$$

(22)

Proof

If $y \in P_{i i}$ then $y = x_i$. Since for every scenario s, ${\varTheta }^1(P_{i i},x_i,s) = 0$,

$$\begin{aligned} R_{i i} = \max _{s \in S^*} \left( {\varTheta }^1(P_{ii},x_{ii},s) - {\varTheta }^k_{\mathrm {opt}}(P,s) \right) = \max _{s \in S^*} \left( - {\varTheta }^k_{\mathrm {opt}}(P,s) \right) \le 0, \end{aligned}$$

so ${\bar{R}}_{i i} = \max \{0, R_{ii}\} = 0$. $\square$

Lemma 4

$$\begin{aligned} \forall l \le r,\quad R'_{l r } \le R_{l r}. \end{aligned}$$

Proof

Recall that $S^*(P_{l r}) \subset S^*$, so

$$\begin{aligned} \forall y \in P_{l r}, \quad R'_{l r}(y) = \max _{s \in S^*(P_{l r})} R_{l r }(y,s) \le \max _{s \in S^*} R_{l r }(y,s)= R_{l r}(y). \end{aligned}$$

Thus

$$\begin{aligned} R'_{l r} = \min _{x_{l} \le y \le x_{r}} R'_{l r}(y) \le \min _{x_{l} \le y \le x_{r}} R_{l r}(y) = R_{l r }. \end{aligned}$$

(23)

$\square$

Lemma 5

Let $d = d\left( {\hat{P}}\right)$ where ${\hat{P}}=\{P_1,P_2,\ldots ,P_k\}$. Then

$$\begin{aligned} \forall y \in P_d,\quad R_{l_d,r_d}(y) = R'_{l_d,r_d}(y), \end{aligned}$$

(24)

and

$$\begin{aligned} R_{l_d,r_d} =R'_{l_d,r_d}. \end{aligned}$$

(25)

Proof

For any $y \in P_d$ set $y_d =y$ and for $i \not = d$ set $y_i \in \left[ x_{l},x_{r_i}\right]$ to be a sink that achieves $R_{l_i,r_i} = R_{l_i,r_i}(y_i)$. Fix ${\hat{Y}}=\{y_1,y_2,\ldots ,y_k\}$.

Set $\alpha = R_{l_d,r_d}$. By the definition of d,

$$\begin{aligned} \forall i< d,\quad \max _{s \in S^*} R_{l_i r_i}(y_i,s) = R_{l_i r_i}(y_i)= R_{l_i r_i}< \alpha \end{aligned}$$

and

$$\begin{aligned} \forall i > d,\quad \max _{s \in S^*} R_{l_i r_i}(y_i,s) = R_{l_i r_i}(y_i) = R_{l_i r_i}\le \alpha . \end{aligned}$$

Furthermore

$$\begin{aligned} \max _{s\in S^*} R_{l_d r_d}(y_d,s) = R_{l_d r_d}(y_d) \ge \min _{l_d \le y_d \le r_d}R_{l_d r_d}(y_d) = \alpha . \end{aligned}$$

Let $s'\in S^*$ be such that $R_{l_d r_d}(y_d,s')= R_{l_d r_d}(y_d)$. Property 2 and the statements above imply that $s'$ is a worst case scenario for $\{{\hat{P}}, {\hat{Y}}\}$ and $P_d$ is the dominant partition for $\{{\hat{P}}, {\hat{Y}}\}$ under scenario $s'$ (following Definition 2). Property 3 then implies the existence of $s^* \in S^*(P_d)$ such that $R_{l_d r_d}(y_d,s^*) = R_{l_d r_d}(y_d,s')$. Since $S^*(P_d) \subset S^*$, this immediately implies

$$\begin{aligned} R'_{l_d,r_d}(y_d) =\max _{s \in S^*(P_d)} R_{l_d r_d}(y_d,s) = \max _{s \in S^*} R_{l_d r_d}(y_d,s) = R_{l_d,r_d}(y_d). \end{aligned}$$

proving Eq. 24. Equation 25 follows from Eq. 24 and the definitions of $R_{l_d,r_d}$, $R'_{l_d,r_d}$:

$$\begin{aligned} R_{l_d,r_d} = \min _{x_{l_d} \le y \le x_{r_d}} R_{l_d,r_d}(y) = \min _{x_{l_d} \le y \le x_{r_d}} R'_{l_d,r_d}(y) = R'_{l_d,r_d}. \end{aligned}$$

$\square$

Lemma 6

Fix ${\hat{P}}=\{P_1,P_2,\ldots ,P_k\}$ with $P_i =[x_{l_i},x_{r_i}]$. Set $d=d\left( {\hat{P}}\right)$, $d' =d'\left( {\hat{P}}\right)$ and ${\bar{d}} = {\bar{d}}\left( {\hat{P}}\right)$. Then

• 1. $R_{l_d r_d} = R'_{l_{d'} r_{d'}} = {\bar{R}}_{l_{{\bar{d}}} r_{{\bar{d}}}}$.

• 2. If $R_{l_d r_d} = 0$, then

  • $d = d'$

  • $\forall i, {\bar{R}}_{l_i r_i}=0$, so ${\bar{d}} = 1$.

• 3. If $R_{l_d r_d} > 0$, then $d = d' = {\bar{d}}$.

Proof

From Lemma 2,

$$\begin{aligned} \max _{1\le i\le k}\left\{ {\bar{R}}_{l_i r_i}\right\} = \max _{1\le i\le k} \left\{ \max \{R_{l_i r_i},\, 0\} \right\} = \max \left\{ \max _{1\le i\le k}\left\{ R_{l_i r_i}\right\} ,\, 0\right\} = \max _{1\le i\le k}\left\{ R_{l_i r_i}\right\} \end{aligned}$$

and thus $R_{l_d r_d} = {\bar{R}}_{l_{{\bar{d}}} r_{{\bar{d}}}}$.

From Lemma 5, $R_{l_d r_d}=R'_{l_d r_d}$. From Lemma 4 and the definition of $d'$,

$$\begin{aligned} R_{l_d r_d} = R'_{l_d r_d} \le R'_{l_{d'} r_{d'}} = \max _{1\le i\le k}\left\{ R'_{l_i r_i}\right\} \le \max _{1\le i\le k}\left\{ R_{l_i r_i}\right\} = R_{l_d r_d}. \end{aligned}$$

(26)

This implies that $R'_{l_d r_d} = R'_{l_{d'} r_{d'}} = R_{l_d r_d}$ completing the proof of (1).

Furthermore, by the definition of $d'$, $d' \le d$. Suppose that $d' < d$. Then, again from Lemma 4, this would imply

$$\begin{aligned} R_{l_d r_d} = R'_{l_{d'} r_{d'}} \le R_{l_{d'} r_{d'}}, \end{aligned}$$

contradicting the definition of d. Thus $d = d'$,

If $R_{l_d r_d} = 0$ then, from (1), ${\bar{R}}_{l_{{\bar{d}}} r_{\bar{d}}}=0$. (2) then follows from the fact that

$$\begin{aligned} \forall i, \quad 0 \le {\bar{R}}_{l_i r_i} \le {\bar{R}}_{l_{{\bar{d}}} r_{{\bar{d}}}} =0. \end{aligned}$$

If $0 < R_{l_d r_d}$, then, from (1)

$$\begin{aligned} {\bar{R}}_{l_d r_d} = \max \{R_{l_d r_d},0\} = R_{l_d r_d} = {\bar{R}}_{l_{{\bar{d}}} r_{{\bar{d}}}}. \end{aligned}$$

Recall that $\forall j< d,\, R_{l_j r_j} < R_{l_d r_d}$. Thus

$$\begin{aligned} \forall j< d,\, {\bar{R}}_{l_j r_j } = \max (0, R_{l_i r_i}) < R_{l_d r_d} = {\bar{R}}_{l_{{\bar{d}}} r_{{\bar{d}}}} \end{aligned}$$

so ${\bar{d}} =d$. Combining with $d = d'$ proves (3). $\square$

Combining the above proves the main result.

Theorem 3

$$\begin{aligned} R_{\max }^k (P) = \min _{{\hat{P}}} \max _{1\le i\le k}\left\{ R_{l_i r_i}\right\} = \min _{{\hat{P}}} \max _{1\le i\le k}\left\{ {\bar{R}}_{l_i r_i}\right\} = \min _{{\hat{P}}} \max _{1\le i\le k}\left\{ R'_{l_i r_i}\right\} . \end{aligned}$$

Proof

Follows directly from Eq. 14 in Theorem 2 and part (1) in Lemma 6. $\square$

The following observation will be quite useful in removing degenerate cases.

Lemma 7

Fix ${\hat{P}}=\{P_1,P_2,,P_k\}$ and set $d = d\left( {\hat{P}}\right)$. If $R_{l_d r_d} =0$, $R'_{l_{d'} r_{d'}}=0$ or ${\bar{R}}_{l_{{\bar{d}}} r_{{\bar{d}}}}=0$ then $R_{\max }^k (P) =0$.

Proof

This follows directly from Lemma 6 and Theorem 3. $\square$

4.2 Recurrence Relations for Minmax Regret

For ${\hat{P}}=\{P_1,P_2,\ldots ,P_k\}$, the values $R_{l_i r_i}$, ${\bar{R}}_{l_i r_i}$, $R'_{l_i r_i}$ can be interpreted as (three different) costs of $P_i = [x_{l_i},x_{r_i}]$. Solving for $R_{\max }^k (P)$ using Theorem 3 is then the problem of finding the minmax costk-partition with these $P_i$ costs. Such partitioning problems can be solved in polynomial time using Dynamic Programming (DP). We encode the corresponding DP recurrences for costs ${\bar{R}}_{l r}$ and $R_{l r}$ in the following straightforward lemma without proof. Note that a corresponding equation also exists for the costs $R_{l r}$ but this would lead to a slower algorithm and is therefore not presented.

Lemma 8

For $0 \le i \le j \le n$ and $1 \le q \le k$ set

$$\begin{aligned} M^q_{i j}&\,{:=}\,&\left\{ \begin{array}{ll} \mathrm{undefined} &{} \ \text{ if } \, j-i< q-1, \\ {\bar{R}}_{i j} &{} \ \text{ if } \, q=1, \\ \min \limits _{i \le t < j} \max \left\{ {\bar{R}}_{i t},\, M^{q-1}_{(t+1) j}\right\} &{} \ \text{ otherwise }. \end{array} \right. \end{aligned}$$

(27)

$$\begin{aligned} M'^q_{i j}&\,{:=}\,&\left\{ \begin{array}{ll} \mathrm{undefined} &{} \ \text{ if } \, j-i< q-1,\\ R'_{i j} &{} \ \text{ if } \, q=1,\\ \min \limits _{i \le t < j} \max \left\{ R'_{i t},\, M'^{q-1}_{(t+1) j}\right\} &{} \ \text{ otherwise }. \end{array} \right. \end{aligned}$$

(28)

Then

$$\begin{aligned} M_{0 n} = \min _{{\hat{P}}} \max _{1\le i\le k}\left\{ {\bar{R}}_{l_i r_i}\right\} = R_{\max }^k (P) = \min _{{\hat{P}}} \max _{1\le i\le k}\left\{ R'_{l_i r_i}\right\} = M'_{0 n}. \end{aligned}$$

If the ${\bar{R}}_{i j}$ ($R'_{i j}$) are precalculated, Eq. 27 (Eq. 28) defines a dynamic program for calculating all of the $M^q_{i j}$ ($M'^q_{i j}$) in $O(n^3 k)$ time.

For fixed i, j, from Definition 9(a), it is not difficult to see how to evaluate $R'_{i j}$ in $O(n^3)$ time (at least in the case when all sinks must be on vertices), thus calculating all the $R'_{i j}$ in $O(n^5)$ time. Once all $R'_{i j}$ are known, Eq. 28 permits calculating $M'^k_{0 n} = \min _{{\hat{P}}} \max _{1\le i\le k}\left\{ R'_{l_ir_i}\right\} = R_{\max }^k (P)$ in $O(n^3 k)$ time, giving an $O(n^5)$ algorithm.

We omit further details because we now present much faster algorithms for calculating $M'^k_{0 n}$. This will be efficient for calculating $R_{\max }^k (P)$ for large k. Monotonicity as introduced in the next subsection will yield a better algorithm for calculating $M^k_{0 n}$. This will be efficient for calculating $R_{\max }^k (P)$ for small k.

4.3 Monotonic Sequences

The following property of the $R_{l r}$ will help speed up the calculations.

Lemma 9

Let $l \le r$. Then

$$\begin{aligned} (\mathrm{a}) \quad R_{l r}\le & {} R_{l(r+1)},\\ (\mathrm{b}) \quad R_{l r}\le & {} R_{(l-1)r}. \end{aligned}$$

Intuitively, increasing the size of a subpath can not decrease its regret.

Proof

We prove (a). The proof of (b) will be symmetric.

Let s be any scenario. and $x_{l} \le y \le x_{r}$. Extending $P_{l r}$ one vertex to the right to create $P_{l (r+1)}$ can not decrease evacuation time so

$$\begin{aligned} {\varTheta }^1(P_{l r},y,s) \le {\varTheta }^1(P_{l (r+1)} ,y,s) \end{aligned}$$

and then

$$\begin{aligned} R_{l r}(y,s)= & {} {\varTheta }^1(P_{ l r},y,s) - {\varTheta }^k_{\mathrm {opt}}(P,s)\\\le & {} {\varTheta }^1(P_{l (r+1)},y,s) - {\varTheta }^k_{\mathrm {opt}}(P,s) = R_{l (r+1)}(y,s). \end{aligned}$$

Since this is true for every scenario s,

$$\begin{aligned} R_{l r}(y) = \max _{s \in S^*} R_{l r}(y,s) \le \max _{s \in S^*} R_{l (r+1)}(y,s) = R_{l (r+1)}(y) \end{aligned}$$

(29)

so

$$\begin{aligned} R_{l r}= \min _{x_l \le y \le x_r} R_{l r}(y) \le \min _{x_l \le y \le x_r} R_{l (r +1)}(y). \end{aligned}$$

(30)

Now suppose $x_r < y \le x_{r +1}$. Then, for every scenario s,

$$\begin{aligned} {\varTheta }^1(P_{ l r},x_r,s) = {\varTheta }_L(P_{l (r+1)},x_r,s) \le {\varTheta }_L(P_{l (r+1)} , y,s) \le {\varTheta }^1(P_{l (r+1)},y,s) \end{aligned}$$

and then

$$\begin{aligned} R_{l r}(x_r,s)= & {} {\varTheta }^1(P_{ l r},x_r,s) - {\varTheta }^k_{\mathrm {opt}}(P,s)\\\le & {} {\varTheta }^1(P_{l (r+1)},y,s) - {\varTheta }^k_{\mathrm {opt}}(P,s) = R_{l (r+1)}(y,s). \end{aligned}$$

Continuing similar to above,

$$\begin{aligned} R_{l r}(x_r) = \max _{s \in S^*} R_{l r}(x_r,s) \le \max _{s \in S^*} R_{l (r+1)}(y,s) = R_{l (r+1)}(y) \end{aligned}$$

so

$$\begin{aligned} R_{l r}= \min _{x_l \le y \le x_r} R_{l r}(y) \le R_{l r}(x_r) \le \min _{x_r < y \le x_{r+1}} R_{l (r +1)}(y) \end{aligned}$$

(31)

Combining Eqs. (30) and (31) yields

$$\begin{aligned} R_{l r}\le & {} \min \left( \min _{x_l \le y \le x_r} R_{l (r +1)}(y),\, \min _{x_r < y \le x_{r+1}} R_{l (r +1)}(y)\right) \\= & {} \min _{x_l \le y \le x_{r +1}}R_{l (r +1)}(y) = R_{l (r +1)} \end{aligned}$$

proving (a). As noted, the proof of (b) is totally symmetric. $\square$

We give this property a name and derive useful properties.

Definition 11

Let $A_{i j}$ be real values defined for all $0 \le i \le j \le n$.

$A_{i j}$ is monotonic if $A_{ii}=0$ and

$$\begin{aligned} \forall 0 \le i \le j< n,\quad A_{i j} \le A_{i (j+1)} \quad \text{ and } \quad \forall 0 < i \le j \le n,\quad A_{i j} \le A_{(i-1) j}. \end{aligned}$$

The useful properties are

Lemma 10

Let $A_{ij}$ and $B_{i j}$ be monotonic. For $i \le j$ define

$$\begin{aligned} C_{i j} \,{:=}\, \left\{ \begin{array}{ll} 0 &{} \text{ if } \, i=j \\ \min _{i \le t< j} \max \{A_{i t} , B_{(t+1)j}\} &{} \text{ if } \, i<j \end{array} \right. \end{aligned}$$

• 1. Then $C_{i j}$ is monotonic.

• 2. For $j >i$ set $t[i,j] = \min \{t \,:\, i \le t < j \text{ and } A_{i t} \ge B_{(t+1)j}\}$.

  (Note: such a t must exist because $A_{i (j-1)} \ge 0 = B_{j j}$.) Then

  $$\begin{aligned}&\forall i \in [i,j],\quad A_{i t}< B_{(t+1)j} \quad \text{ if } \text{ and } \text{ only } \text{ if } \quad t < t[i,j], \end{aligned}$$

  (32)
  $$\begin{aligned}&\qquad C_{i j} = \min \{A_{i t[i,j]},\, B_{t[i,j] j}\} \end{aligned}$$

  (33)

• 3. $\forall 1 \le i< j < n, \quad t[i,j] \le t[i, j+1]$

Proof

• 1. From the monotonicity of $B_{i j}$,

  $$\begin{aligned} \forall t,\, i \le t < j, \quad B_{(t+1)j} \le B_{(t+1)(j+1)} \end{aligned}$$

  so

  $$\begin{aligned} \max \{A_{i t} , B_{(t+1)j}\} \le \max \{A_{i t} , B_{(t+1)(j+1)}\}. \end{aligned}$$

  From the monotonicity of $A_{i j}$ and the fact $B_{j j} = B_{(j+1) (j+1)} =0$,

  $$\begin{aligned} \max \{A_{i (j-1)} , B_{j j}\} = A_{i (j-1)} \le A_{i j } =\max \{A_{i j} , B_{(j+1)(j+1)}\}. \end{aligned}$$

  Thus

  $$\begin{aligned} C_{i j} = \min _{i \le t< j} \max \{A_{i t} , B_{(t+1)j}\} \le \min _{i \le t < j+1} \max \{A_{i t} , B_{(t+1)(j+1)}\} = C_{i (j+1)}. \end{aligned}$$

  The proof that $C_{i,j} \le C_{(i-1) j}$ is symmetric.

• 2. If $j = i+1$ then $t[i,j] = i$ and Eqs. 32 and 33 are trivially satisfied with $C_{i j} = \max \{A_{i i}, B_{ jj}\} =0 = \min \{A_{i i}, B_{i j}\}$. Otherwise, $j > i+1$. From the definition of t[i, j], $\forall i \le t < t[i,j],\quad A_{i t} \le B_{(t+1)j}$. Next, by monotonicity, and the definition of t[i, j],

  $$\begin{aligned} \forall t[i,j] \le t < j,\quad A_{i t} \ge A_{i t[i,j]} \ge B_{(t[i,j]+1) j} \ge B_{(t+1)j} \end{aligned}$$

  proving Eq. 32. To prove Eq. 33 note that by monotonicity,

  $$\begin{aligned} \min _{i \le t< t[i,j]} \max \{A_{i t} , B_{(t+1)j}\} = \min _{i \le t < t[i,j]} B_{(t+1) j} = B_{t[i,j] j} \end{aligned}$$

  and

  $$\begin{aligned} \min _{t[i,j] \le t< j} \max \{A_{i t} , B_{(t+1)j}\} = \min _{t[i,j] \le t < j} A_{i,t} = A_{i,t[i,j]} \end{aligned}$$

• 3. Note that, if $A_{i t} <B_{(t+1) j}$ then, by monotonicity, $A_{i t} \le B_{(t+1) j} \le B_{(t+1) (j+1)}$ and the proof follows from part (2).

$\square$

Monotonic sequences are relevant because Lemmas 3 (Eq. 22) and 9 imply that the ${\bar{R}}_{ i j}$ are monotonic and thus from Lemma 10(1)

Corollary 1

For every fixed q, $0 \le q \le k$ the $M^q_{i,j}$ defined in Lemma 8 are monotonic.

Note For later use we note that Lemma 9 and Corollary 1 no longer hold if $R_{l r}$ is replaced by $R'_{l r}$. Thus is because, after this substitution, Eqs. 29 and 30 no longer remain valid because $S^*(P_{l r}) \not \subseteq S^*(P_{l(r+1)})$, so it is not necessarily true that $\max _{s \in S^*(P_{l r})} R_{l r}(s,y) \le \max _{s \in S^*(P_{l (r+1)})} R_{l (r+1)}(s,y)$. Thus, the $R'_{l r}$ are not necessarily monotonic. This fact will have later implications in the algorithmic design.

5 ${\varTheta }^k(P,x,s)$ and $R_{i j}$: Properties and Calculation

Equations 27 and 28 lead directly to two different dynamic programming solutions for calculating the minmax regret; one based on ${\bar{R}}_{i j}$ and the other on $R'_{i j}$. Using them requires efficient calculation of $R_{i j}$ and $R'_{i j}$ which first requires efficient calculation of ${\varTheta }^k(P,s)$.

Earlier papers, e.g., [9, 16, 20, 27, 34], in this area have already developed techniques for fast calculation of ${\varTheta }^k(P,s)$ for fixed s. The closest to our needs is the Critical Vertex Tree data structure of [9]. A straightforward modification of [9]’s design yields the following:

Lemma 11

The Critical Vertex Tree (CVT) Data Structure can be built in O(n) time and, once built, permits the following operations:

Let $i \le j$ and set $P_{i j}= [x_i,x_j]$. Let $0 \le t_1 \le t_2 \le n$ and set $s = s^*_B(t_1,t_2)$ as introduced in Definition 6. Then all of the below can be calculated in $O(\log n )$ time.

• 1. ${\varTheta }_L(P_{i j},x,s)$ and ${\varTheta }_R(P_{i j},x,s)$ for any $x \in P_{i j}$.

• 2. ${\varTheta }^1(P_{i j},s)$ and the value $x^*$ such that ${\varTheta }^1(P_{i j}, s) = \max \big \{{\varTheta }_L(P_{i j},x^*,s), {\varTheta }_R(P_{i j},x^*,s)\big \}$.

• 3. For any $\alpha > 0$, $\max \{x' \in P_{i j} \,:\, {\varTheta }_L(P_{i j},x',s) \le \alpha \}$.

• 4. For any $x \in P_{i j}$ and $\alpha > 0$, $\max \{j' \le j\,:{\varTheta }_R\left( [x,x_{j'}],x,s\right) \le \alpha \}$.

We note that [9] defines the Critical Vertex Tree for a fixed scenario s, provides the O(n) construction algorithm, proves point (1) and gives an $O(\log ^2 n)$ (and not $O(\log n)$) algorithm for (2). In the “Appendix” (Sect. 8) we describe the modifications required to extend their construction to yield the full strength of Lemma 11.

The remainder of this section, though, assumes the correctness of Lemma 11 and describes how it permits fast construction of $R_{i j}$ and $R'_{i j}$. The first step is to show that it permits fast calculation of ${\varTheta }^k_{\mathrm {opt}}(P,s)$ for $s \in S^*$.

For simplification, the derivations often use the following substitution.

Definition 12

Let s be fixed. For $i \le j$, define

$$\begin{aligned} A^q_{i j} \,{:=}\, {\varTheta }^q_{\mathrm {opt}}(P_{i j},s). \end{aligned}$$

Lemma 12

For fixed s and all q, $A^q_{i j}$ is a monotonic sequence.

Proof

Adding a vertex to a subpath can only increase its 1-sink evacuation time so $A^1_{i j} \le A^1_{i (j+1)}$ and $A^1_{(i-1) j} \le A^1_{i j}$. Since $A^1_{i i}=0$, the sequence $A^1_{i j}$ is monotonic.

The proof that $A^q_{i j}$ is monotonic will be by induction on q. Assume that $A^{q-1}_{i j}$ is monotonic (as has just been shown for $q=2$). Now note that

$$\begin{aligned} A^q_{i j} = {\varTheta }^q_{\mathrm {opt}}(P_{i j},s)= & {} \min _{i \le t< j} \max \{{\varTheta }^1_{\mathrm {opt}}(P_{i t},s), {\varTheta }^{q-1}_{\mathrm {opt}}(P_{(t+1)j},s)\}\\= & {} \min _{i \le t < j} \max \{ A^{1}_{i t},\, A^{q-1}_{(t+1) j} \}, \end{aligned}$$

so by Lemma 10, $A^q_{i j}$ is also monotonic. $\square$

The algorithm for calculating the optimum value${\varTheta }^q_{\mathrm {opt}}(P_{i j},s)$ will utilize the following feasibility test as a subroutine.

Lemma 13

Assume $i \le j$, $\alpha \ge 0$ and $s = s^*_B(t_1,t_2)$. Define

$$\begin{aligned} Feasible(q: i,j, \alpha ,s) \,{:=}\, \left\{ \begin{array}{ll} \mathrm{TRUE}, &{} \text{ if } {\varTheta }^q_{\mathrm {opt}}(P_{i j},s) \le \alpha ,\\ \mathrm{FALSE}, &{} \text{ if } {\varTheta }^q_{\mathrm {opt}}(P_{i j},s) > \alpha . \end{array} \right. \end{aligned}$$

Assuming a pre-constructed CVT, $Feasible(q: i,j, \alpha ,s)$ can be calculated in $O(q \log n)$ time.

Proof

Note that if $i=j$, then $A^q_{i j} = {\varTheta }_{\mathrm {opt}}^1(P_{i i},s)=0$, so $Feasible(q: i,j,\alpha ,s)=\text{ TRUE }$.

${\hbox {If} \, i< j \, \hbox {and} \, q=1:}$

$A^1_{i j} = {\varTheta }_{\mathrm {opt}}^1(P_{i j},s) \le \alpha$ can be checked in $O (\log n)$ time by using Lemma 11 to directly calculate ${\varTheta }_{\mathrm {opt}}^1(P_{i j},s)$.

${\hbox {If} \, i< j \, \hbox {and} \, q > 1:}$

Set

$$\begin{aligned} t\,{:=}\, \max \{ t' \,: t' \le j \text{ and } {\varTheta }_{\mathrm {opt}}^1(P_{i t'},s) \le \alpha \}. \end{aligned}$$

This can be calculated in $O(\log n)$ time by first using Lemma 11(3) to find

$$\begin{aligned} x'' = \max \{x' \in P_{ij}:\, {\varTheta }_L(P_{i j},x',s) \le \alpha \} \end{aligned}$$

and then using Lemma 11(4) to find

$$\begin{aligned} t = \max \{j' \,:\, j' \le j \text{ and } {\varTheta }_R(P_{i j'},x'',s) \le \alpha \}. \end{aligned}$$

If $t =j$ then

$$\begin{aligned} A^q_{i t} = {\varTheta }_{\mathrm {opt}}^q(P_{i t},s) \le {\varTheta }_{\mathrm {opt}}^1(P_{i t},s) \le \alpha \end{aligned}$$

so $Feasible(q: i,j,\alpha ,s)=\text{ TRUE }$. If $t < j$, then $A^1_{i t} \le \alpha$ and $A^1_{i (t+1)} >\alpha$. From the monotonicity of $A^q_{i,j}$ in Lemma 12,

$$\begin{aligned} A^{q}_{i j} \le \alpha \quad \text{ if } \text{ and } \text{ only } \text{ if } \quad A^{q-1}_{(t+1) j}\le \alpha . \end{aligned}$$

So, if $t < j$,

$$\begin{aligned} Feasible(q: i,j,\alpha ,s)= Feasible(q-1: t+1,j,\alpha ,s). \end{aligned}$$

(34)

Thus $Feasible(q: i,j,\alpha ,s)$ can be implemented via a recursive procedure that does $O(\log n)$ work to calculate t and then calls $Feasible(q-1: t+1,j,\alpha ,s)$. When $q=1$ the evaluation can be done in $O( \log n)$ time, so the full evaluation of $Feasible(q: i,j,\alpha ,s)$ can be implemented in $O(q \log n)$ time as required. $\square$

Lemma 14

Let $s = s^*_B(t_1,t_2)$ and $i < j$. Assuming a pre-constructed CVT, ${\varTheta }^k_{\mathrm {opt}}(P_{i j},s)$ can be calculated in $O(k^2 \log ^2 n)$ time.

Proof

Let $q \le k$. Set

$$\begin{aligned} t_q[i,j] = \min \{t \,:\, i \le t < j \text{ and } A^1_{i t} \ge A^{q-1}_{(t+1)j}\}. \end{aligned}$$

Lemmas 10 and 12 guarantee that, if $t \in [i,j]$ then

$$\begin{aligned} i \le t< t_q[i,j] \quad \Leftrightarrow \quad A^1_{i t} < A^{q-1}_{(t+1)j}, \end{aligned}$$

(35)

and

$$\begin{aligned} A^{q}_{i j} = \min \left\{ A^1_{i t_q[i,j]},\, A^{q-1}_{t_q[i,j] j}\right\} . \end{aligned}$$

(36)

Equation 35 implies that $t_q[i,j]$ can be found via binary search using $O(\log n)$ queries of the form ($t < t_q[i,j]?)$ which are equivalent to the queries $(A^{1}_{i t} < A^{q-1}_{(t+1)j}?)$. This can be implemented by

• 1. Calculating $\alpha = A^1_{i t}={\varTheta }^1_{\mathrm {opt}}(P_{i t},s)$ in $O( \log n)$ time using Lemma 11 (1);

• 2. then noting that $A^{1}_{i t} < A^{q-1}_{(t+1)j}$ iff $Feasible(q-1: t+1,j, \alpha ,s)= \text{ FALSE }$.

From Lemma 13, the time for one query is $O(q \log n)$ so the total binary search time to find $t_q[i,j]$ is $O(q \log ^2 n)$. The full algorithm³ to calculate $A^q_{i j}$ is then

• 1. If $q=1$, calculate $A^1_{i j}$ in $O(\log n)$ time using Lemma 11 (1)

• 2. Else if $q>1$

• 3.       Find $t_q[i,j]$ in $O(q \log ^2 n)$ time

• 4.       Calculate $A^1_{i t_q[i,j]}$ in $O(\log n)$ time using Lemma 11 (1)

• 5.       Recursively calculate $A^{q-1}_{t_q[i,j] j}$

• 6.       Return $\min \left\{ A^1_{i t_q[i,j]}, A^{q-1}_{t_q[i,j] j} \right\}$.

Let $F_q(n)$ be the time required to calculate $A^q_{i j}$ where $n = j-i +1$. The recurrence relation is then

$$\begin{aligned} F_q(n) = \left\{ \begin{array}{ll} O(\log n) &{} \text{ if } \, q=1,\\ F_{q-1}(n) + O(q \log ^2 n) &{} \text{ if } \, q > 1, \end{array} \right. \end{aligned}$$

which solves out to $F_k(n) = O(k^2 \log ^2 n)$. $\square$

5.1 Evacuation Costs for Sinks not on Vertices

The following simple observation about the linearity of evacuation as the sink moves along an edge between two vertices wil be needed. It follows directly from the evacuation cost formulas in Eqs. 1 and 2:

Lemma 15

Suppose $i < k \le j$ and $x \in P_{(k-1) k}$. For any scenario s, if $x_{k-1} < x \le x_k$, then

$$\begin{aligned} {\varTheta }_L(P_{i j},x,s) = {\varTheta }_L(P_{i k},x_k,s)- \tau (x_k-x) = {\varTheta }_L(P_{i k},s) - \tau (x_k-x) \end{aligned}$$

and if $x_{k-1} \le x < x_k$,

$$\begin{aligned} {\varTheta }_R(P_{i j},x,s)= & {} {\varTheta }_R(P_{(k-1) j},x_{k-1},s)- \tau (x-x_{k-1}) \\= & {} {\varTheta }_R(P_{(k-1) j},s) - \tau (x-x_{k-1}). \end{aligned}$$

${\varTheta }_L(P_{i j},x_k,s)$ is the time required for the last piece of flow from within $P_{i (k-1)}$ to reach $x_k$. The intuition for the first equation is that no congestion can occur inside an edge so the last flow reached x exactly $\tau (x_k-x)$ before it reached $x_k$. The intuition for the second equation is similar.

5.2 Strict Unimodality and Its Applications

Definition 13

Let f(x) be a function on a real interval $I=[y,z]$. f(x) is strictly unimodal if there exists some $x^* \in I$ such that f(x) is monotonically decreasing in $[x,x^*]$ and monotonically increasing in $[x^*,y]$. It is not necessary that f(x) be continuous. Note that $x^*$ is the unique minimum location of f(x).

Strictly unimodal functions arise quite naturally. The proof of the following lemma is straightforward and therefore omitted.

Lemma 16

Let f(x), g(x) be, respectively, monotonically increasing and decreasing functions on I. Then $h(x) = \max \left\{ f(x),g(x)\right\}$ is a strictly unimodal function on I.

Finally, the maximum of strictly unimodal functions is easily shown to be strictly unimodal.

Lemma 17

If $f_1(x)$ and $f_2(x)$ are both strictly unimodal on I then $f(x) = \max \left\{ f_1(x),f_2(x)\right\}$ is also strictly unimodal on I.

More generally, if $f_i(x)$, $i=1,2,\ldots ,j$ are all strictly unimodal on I then $f(x) = \max _{1 \le i \le j} f_i(x)$ is also strictly unimodal on I.

Strictly unimodal functions arise in our problem due to the following:

Lemma 18

Let $i \le j$ and $s \in S$. Then

• 1. ${\varTheta }^1(P,x,s)$ is a strictly unimodal function on P as a function of x.

• 2. $R_{ij}(y,s)$ is a strictly unimodal function on $P_{i j}$ as a function of y.

• 3. $R_{ij}(y)$ is a strictly unimodal function on $P_{i j}$ as a function of y.

• 4. $R'_{ij}(y)$ is a strictly unimodal function on $P_{i j}$ as a function of y.

Proof

• 1. This follows directly from the definition

  $$\begin{aligned} {\varTheta }^1(P,x,s)= & {} \max \left\{ {\varTheta }_{L}(P,x,s),{\varTheta }_{R}(P,x,s)\right\} , \end{aligned}$$

  (37)

  ${\varTheta }_{L}(P,x,s)$ being monotonically increasing in x, ${\varTheta }_{R}(P,x,s)$ being monotonically increasing in x and Lemma 16.

• 2. From the definition

  $$\begin{aligned} R_{i j}(s,y) = {\varTheta }^1(P_{i j},y,s) - {\varTheta }^k_{\mathrm {opt}}(P,s). \end{aligned}$$

  Part (1) states that ${\varTheta }^1(P_{i j},y,s)$ is strictly unimodal. Subtracting a constant from a strictly unimodal function leaves another strictly unimodal function.

• 3. Apply Part (2) and Lemma 17 to

  $$\begin{aligned} R_{i j}(y) = \max _{s\in S^*}\left\{ R_{i j}(y,s)\right\} . \end{aligned}$$

• 4. Again apply Part (2) and Lemma 17, but this time to

  $$\begin{aligned} R'_{i j}(y) = \max _{s\in S^*(P_{i j})}\left\{ R_{i j}(y,s)\right\} . \end{aligned}$$

$\square$

Binary searching on Strictly Unimodal functions is known to be “easy”.

Lemma 19

Let f(x) be a strictly unimodal function defined in [x, y] and $x^*$ the location of its unique minimum value. Let $x=x_1< x_2 < \ldots x_n =y$ be a sequence of points and g(n) the time required to evaluate $g(x_i)$ for any i. Then, in $O(g(n) \log n)$ time, binary search can determine the index

$$\begin{aligned} t = \max \{i \,:\, 1 \le i \le n,\, \text{ and } \ x_i \le x^* \} \end{aligned}$$

Note that if $t=n$ then $x^* = x_n=y$. Otherwise $x_t \le x^* < x_{t+1}$.

This immediately leads to the major technical construction lemma

Lemma 20

Let $i \le j$ be integers, $s\in S^*$ a scenario, $x \in P_{i j}$,

$$\begin{aligned} \alpha (n)= & {} \text{ Time } \text{ needed } \text{ to } \text{ evaluate } \, {\varTheta }^k_{\mathrm {opt}}(P,s) ,\\ \beta (i,j, s)= & {} \text{ Time } \text{ needed } \text{ to } \text{ evaluate } \, {\varTheta }_{L}(P_{i j},x,s) \, \text{ and } \, {\varTheta }_{R}(P_{i j},x,s). \end{aligned}$$

Recall that

$$\begin{aligned} (\mathrm{a}) \ R_{ij} = \min _{x_{i} \le y \le x_{j}} R_{i j}(y) \quad \text{ and }\quad (\mathrm{b}) \ R'_{ij} = \min _{x_{i} \le y \le x_{j}} R'_{i j}(y). \end{aligned}$$

(38)

Then

(a) $R_{ij}$ and the y at which the minimum is achieved in Eq. 38 (a) can be evaluated in time

$$\begin{aligned} O\left( n^2 \alpha (n) + n^2 \beta (i,j, s) \log n\right) . \end{aligned}$$

(b) $R'_{ij}$ and the y at which the minimum is achieved in Eq. 38 (b) can be evaluated in time

$$\begin{aligned} O\left( (j - i +1) \alpha (n) +(j - i +1) \beta (i,j, s) \log n\right) . \end{aligned}$$

Proof

(a) Use $O(n^2 \alpha (n))$ time to calculate ${\varTheta }^k_{\mathrm {opt}}(P,s)$ for all the $O(n^2)$ scenarios $s \in S^*$. Store these $O(n^2)$ values so that they can be retrieved in O(1) time.

For fixed s and y, calculating

$$\begin{aligned} R_{ij}(y,s) = \max \left\{ {\varTheta }_{L}(P_{i j},y,s),{\varTheta }_{R}(P_{i j},y,s)\right\} - {\varTheta }^k_{\mathrm {opt}}(P,s) \end{aligned}$$

only requires an additional $O(\beta (i,j, s))$ time.

$R_{ij}(y)$ can then be evaluated in $O(n^2 \beta (i,j, s) )$ time by evaluating $R_{ij}(y,s)$ at each of the $O(n^2)$$s\in S^*$ and returning the maximum. Call such a calculation of $R_{ij}(y)$ a “query”.

Since $R_{ij}(y)$ is strictly unimodal as a function of y, there exists a unique location $x^*$ at which it achieves its minimum.

Using $O(\log n)$ queries, Lemma 19 finds either that $x^* = x_{j}$ or returns a t such that $x^* \in [x_t, x_{t+1})$.

In the first case, the argument above permits calculating $R_{ij}(x^*)=R_{ij}(x_j)$ in $O(n^2 \beta (i,j, s) )$ time.

In the second case, the same argument permits calculating $R_{ij}(x_t)$ in $O(n^2 \beta (i,j, s))$ time.

If $x^* \not = x_t$ then, $x^* = x_t + \delta$ for some $\delta > 0$ and, from Lemma 15,

$$\begin{aligned} {\varTheta }_{R}(P_{i j},x_t + \delta ,s)= & {} {\varTheta }_R(P_{i j}, x_t,s) - \tau (x^*-x_t)\\ {\varTheta }_{L}(P_{i j},x_t + \delta ,s)= & {} {\varTheta }_L(P_{i j}, x_{t+1},s) - \tau (x_{t+1}-x^*) \end{aligned}$$

Plugging in the definitions and collecting terms yields, $\forall x \in (x_t, x_{t+1})$,

$$\begin{aligned} R_{i j}(x, s)= & {} \max \Bigl \{ {\varTheta }_R(P_{i j}, x_t,s) - {\varTheta }^k_{\mathrm {opt}}(P,s) - \tau (x-x_t), \\&\qquad {\varTheta }_R(P_{i j}, x_{t+1},s) - {\varTheta }^k_{\mathrm {opt}}(P,s)- \tau (x_{t+1}-x) \Bigr \}\\= & {} \max \Bigl \{ A_s - \tau x,\, B_s + \tau x \Bigr \} \end{aligned}$$

where $A_s$ and $B_s$ are appropriately defined constants. Thus $\forall x \in (x_t, x_{t+1})$,

$$\begin{aligned} R_{ij}(x)= & {} \max _{s\in S^*}\left\{ R_{ij}(x,s)\right\} \\= & {} \max _{s\in S^*}\max \Bigl \{A_s - \tau x,\, B_s + \tau x\Bigr \}\\= & {} \max \left\{ \max _{s\in S^*} \{A_s -\tau x\}, \ \max _{s\in S^*} \{B_s + \tau x\} \right\} \\= & {} \max \left\{ \left( \max _{s\in S^*} A_s\right) - \tau x, \ \left( \max _{s\in S^*} B_s\right) + \tau x \right\} \\= & {} \max \left\{ A - \tau x, B+ \tau x\right\} \end{aligned}$$

where $A=\max _{s\in S^*} A_s$, $B= \max _{s\in S^*} B_s$. If the $A_s,B_s$ and thus the A, B were known then, by linearity, finding the unique $x^* \in [x_t,x_{t+1})$ such that

$$\begin{aligned} R_{i,j}(x^*) = \min _{x \in [x_t,x_{t+1})} R_{i j}(x) = \min \left( R_{i j}(x_t),\, \min _{x \in (x_t,x_{t+1})} R_{i j}(x) \right) \end{aligned}$$

needs only O(1) time. Since $A_s$ and $B_s$ can be calculated in a further $O(|S^*| (\alpha (n) +\beta (i,j, s)))$ time where $|S^*| = O(n^2)$, the proof is complete.

(b) Start by spending $O((j - i +1) \alpha (n))$ time calculating ${\varTheta }^k_{\mathrm {opt}}(P,s)$ for all the $O((j - i +1))$ scenarios $s \in S^*(P_{i j})$. The evaluation of $R'_{i j}$ is exactly the same as that of $R'_{i j}$ in (a) except that $s \in S^*$ is replaced by $s \in S^*(P_{i j})$. Since $|S^*(P_{i j})| = O(j-i +1)$ this would just replace every $n^2$ in the analysis with $|j-i +1|$ which is the claimed result. $\square$

5.3 Quick Construction of $R_{i j}$ and $R'_{i j}$

The tools just developed provide quick proofs of the following two lemmas.

Lemma 21

Assume a pre-constructed CVT. For any $i < j$, $R_{i j}$ can be evaluated in $O(n^2 k^2 \log ^2 n)$ time and can be evaluated in $R'_{i j}$ in $O( |j-i+1| k^2 \log ^2 n)$ time.

Proof

Lemma 11 immediately provides that $\forall s \in S^*$, $\beta (i,j, s) = O(\log n)$.

Lemma 14 gives $\alpha (n) = O(k^2 \log ^2 n)$.

Plugging back into Lemma 20 completes the proof. $\square$

Lemma 22

All $O(n^2)$$R'_{i j}$ can be constructed in $O(n^3 \log n)$ total time.

Proof

First use O(n) time to construct the CVT.

Next calculate ${\varTheta }^k_{\mathrm {opt}}(P,s)$ for each of the $O(n^2) \, s \in S^*$. As previously mentioned, [7] describes how to calculate one ${\varTheta }^k_{\mathrm {opt}}(P,s)$ in $O(n \log n)$ time so this takes $O(n^3 \log n)$ time. Store the values in an array so each can be accessed in O(1) time.

For fixed i, j, Lemma 11 permits calculating ${\varTheta }_L(P_{i j},x_j,s)$ and ${\varTheta }_R(P_{i j},x_i,s)$ in $O( \log n)$ time. Use $O(n^2 \log n)$ time⁴ to calculate these for all pairs i, j and then store the $O(n^2)$ values in an array so that they can be accessed in O(1) time.

Then apply Lemma 20 with $\alpha (n)= O(1)$ and $\beta (i,j, s) = O(1)$ to see that we can calculate $R'_{i j}$ in $O(|j -i +1| \log n) = O(n \log n)$ time. Thus, all $O(n^2)$$R'_{i j }$ can be calculated in $O(n^3 \log n)$ time. $\square$

6 Algorithm Design

The tools developed now permit designing efficient algorithms for calculating the minmax regret value $R_{\max }^k (P)$ and the associated $\{{\hat{P}}^*,{\hat{Y}}^*\}$ that achieve that value.

Section 6.1 provides a simple dynamic programming algorithm based on Eq. 27 and $R'_{i j}$ that runs in $O(n^3 \log n)$ time, independent of k.

Section 6.2 combines Eq. 28 and the monotonicity of the $R_{ i j}$ to develop a $O(n^2 k^2 \log ^{k+1} n)$ time nested binary-search algorithm.

If the $R'_{i j}$ were also monotonic, then directly replacing the $R_{i j}$ in Sect. 6.2 with $R'_{i j}$ would immediately lead to an improved $O(n k^2 \log ^{k+1} n)$ algorithm. Unfortunately, this is not necessarily true, so that approach fails. The relationship between the $R_{i j}$ and $R'_{i j}$ derived in Lemma 6, though, will permit modifying the algorithm in Sect. 6.2 to run in $O(n k^2 \log ^{k+1} n)$ by simulating sequences of calls to $R_{i j}$ with calls to $R'_{i j}$.

This modification is first illustrated for the simpler $k=2$ case in Sect. 6.3 and then generalized to all k in Sect. 6.4.

The algorithm for $k=2$ runs in $O(n \log ^{3} n)$, improving the previously best known $O(n \log ^4 n)$ algorithm of [9]. To put this into context we note that the algorithm of [9] was actually based on the properties in Sects. 3 and 4 as quoted from an unpublished earlier version [2] of this paper combined with their earlier version of the CVT. Unwinding [9]’s algorithm, it can be seen that the $O(\log n)$ improvement for the $k=2$ case primarily comes from the $O(\log n)$ improvement to the CVT in our Lemma 11 (2).

6.1 A Simple Dynamic Program

For $q=0,1,\ldots ,k$ set $M'(q:i) \,{:=}\, M'^q_{i n}$ as defined in Lemma 8. Then

$$\begin{aligned} M'(q:i) = \left\{ \begin{array}{lcl} \mathrm{undefined} &{}&{} \text{ if } \, q > 1 \, \text{ and } \, n-i< q-1 \\ R'_{i n} &{} \quad &{}\text{ if } \, q=1 \\ \min \limits _{i \le t < n} \max \left\{ R'_{i t}, M'(q-1: t+1)\right\} &{}&{} \text{ otherwise } \end{array} \right. \end{aligned}$$

(39)

From Theorem 3, $M'(k:0) = M'^k_{0 n}=R_{\max }^k (P)$. Use Lemma 22 to calculate all of the $R'_{i,j}$ values in $O(n^3 \log n)$ time, and then DP Eq. 39 to fill in all of the $M'(q:i)$ table entries in $O(n^2 k)$ time (O(n) time per entry) leading to

Theorem 4

For all $k \le n$,

$$\begin{aligned} R_{\max }^k (P) =\min _{\{{\hat{P}},{\hat{Y}}\}} R_{\max }(\{{\hat{P}},{\hat{Y}}\}) = M'^k_{0 n} \end{aligned}$$

can be calculated in $O(n^3\log n)$ time.

Note that this algorithm actually calculates the values $R_{\max }^k (P)$ for all $k\le n$, not just for one specific k. Also, the dynamic program can be unwound using backtracking to find the $\{{\hat{P}}^*,{\hat{Y}}^*\}$ that achieves the minimum value and the worst case scenario associated with it.

6.2 A First Binary Search Based Algorithm

For $q=0,1,\ldots ,k$, set $M(q:i) \,{:=}\, M^q_{i n}$ as defined in Eq. 28. Then

$$\begin{aligned} M(q:i) = \left\{ \begin{array}{lcl} \mathrm{undefined} &{}&{} \text{ if } \, q > 1 \, \text{ and } \, n-i< q-1\\ {\bar{R}}_{j n} &{} \quad &{}\text{ if } \, q=1 \\ \min \limits _{i \le t < n} \max \left\{ {\bar{R}}_{i t}, M(q-1: t+1\right\} &{}&{} \text{ otherwise } \end{array} \right. \end{aligned}$$

(40)

Using Theorem 3 and Lemma 8, our goal is to calculate $M(k:0) = M^k_{0 n}=R_{\max }^k (P)$. This will be sped up by the fact (Corollary 1) that the $M^q_{i j}$ are monotonic.

From Lemma 10 and Corollary 1

$$\begin{aligned} M^q_{i n} = \min _{i \le t < n} \max \left\{ {\bar{R}}_{i t},\, M^{q-1}_{(t+1) n}\right\} = \min \left\{ {\bar{R}}_{i t_q[i,n]},\, M^{q-1}_{t_q[i,n] n}\right\} \end{aligned}$$

(41)

where

$$\begin{aligned} t_q[i,n] = \min \{t \,:\, i \le t < n \ \mathrm{and} R_{i t} \ge M^{q-1}_{(t+1)n}\} \end{aligned}$$

(42)

and $t_q[i,n]$ satisfies

$$\begin{aligned} \forall t \in [i,n],\quad {\bar{R}}_{i t}< M^{q-1}_{(t+1)n} \quad \text{ if } \text{ and } \text{ only } \text{ if } \quad \ t < t_q[i,n]. \end{aligned}$$

(43)

The algorithm binary-searches to find $t_q[i,n]$ and then compares the two possibilities on the right hand side of Eq. 41 to find the correct answer.

To formalize this idea, for $\ell _q, u_q$ satisfying $i \le \ell _q \le u_q < n$, define

$$\begin{aligned} M(q: i, \ell _q, u_q) \,{:=}\, \min _{\ell _q \le t \le u_q} \max \left\{ {\bar{R}}_{i t},\, M^{q-1}_{(t+1) n}\right\} . \end{aligned}$$

(44)

Definition 14

The parameters of $M(q: i, \ell _q, u_q)$ satisfy the sandwich condition if $\ell _q \le t_q[i,n] \le u_q$.

If $M(q: i, \ell _q, u_q)$ satisfies the sandwich condition then, from Eqs. 41, 42, 43,

$$\begin{aligned} M(q: i, \ell _q, u_q) = \min _{\ell _q \le t \le u_q} \max \left\{ {\bar{R}}_{i t},\, M^{q-1}_{(t+1) n}\right\} = \min \left\{ {\bar{R}}_{i t_q[i,n]},\, M^{q-1}_{t_q[i,n] n}\right\} = M^{q}_{i n}, \end{aligned}$$

leading to

Property 5

If $M(q: i, \ell _q, u_q)$ satisfies the sandwich condition then

$$\begin{aligned} M(q: i, \ell _q, u_q) = M(q:i) = M^q_{i n}. \end{aligned}$$

Note that $i \le t_q [i,n] <n$, so

Property 6

$\forall \, i,q$, $M(q: i, i, n-1)$ satisfies the sandwich condition.

This fact will be used often below. As a special case, Property 6 implies

$$\begin{aligned} \min _{\{{\hat{P}},{\hat{Y}}\}} R_{\max }(\{{\hat{P}},{\hat{Y}}\}) =M^k_{0 n}=M(k:0,0,n-1). \end{aligned}$$

Fig. 6

BIN1—the first iterated binary search algorithm. Calling $M(k: 0,0,n-1)$ returns the correct answer $M^k_{0 n} =R_{\max }^k (P)$

BIN1, a recursive algorithm for evaluating $M(q: i, \ell _q, u_q)$ satisfying the sandwich condition, is presented in Fig. 6. Calling $M(k: 0,0,n-1)$ returns the final solution. Without providing details, we note that BIN1 can be easily modified to find the $\{{\hat{P}},{\hat{Y}}\}$ that achieves the minimum and the worst case scenario associated with it. To prove correctness of BIN1 we first show that it terminates, then that all recursive calls satisfy the sandwich condition and, finally, that if the calls satisfy the sandwich condition they terminate with the correct solution.

First note that this algorithm always terminates because all recursive calls from $M(q: i, \ell _q, u_q)$ either decrement q or reduce $u_q - \ell _q$.

Next note that if the parameters of a $M(q: i, \ell _q, u_q)$ call satisfies the sandwich condition then all of the recursive calls it makes satisfy the condition as well. For the calls on lines 2(b)(A) and 2(c)(A) this follows from Property 6. For cases 1(c) and 2(c) the sandwich condition imposes ${\bar{R}}_{i \ell _q} \le {\bar{M}}^{q-1}_{(\ell _q +1) n}$. By setting m to be the midpoint between $\ell _q$ and $u_q$ and checking whether or not ${\bar{R}}_{i m } \le {\bar{M}}^{q-1}_{(m +1) n}$ monotonicity implies whether $t_q[i,n]$ is to the left or right of m and BIN1 makes a recursive call in the appropriate half range containing $t_q[i,n]$, maintaining the sandwich condition. Thus the recursive calls on lines 1(c)(A), 1(c)(B), 2(c)(B) and 2(c)(C) all also satisfy the sandwich condition.

Finally, for correctness, note from the sandwich condition, (41) and (42)

• if $\ell _q = u_q = i$, then $0 = {\bar{R}}_{i i} \ge M^{q-1}_{(i+1) n}$ so $M^{q}_{i n} =0$

• if $\ell _q = u_q \not = i$, then $t_q[i,n] = \ell _q$ and $M^{q}_{i n} = \min \{{\bar{R}}_{i \ell _q}, M^{q-1}_{\ell _q n}\}$.

These are subcases (a) and (b) in cases (1) and (2). Thus the algorithm is correct when $\ell _q = u_q$. As noted above, when $\ell _q < u_q$, i.e., subcase (c) in both cases, the algorithm recurses by making a correct call that maintains the sandwich condition. The correctness of the algorithm then follows from simple induction (Fig. 7).

Fig. 7

The diagram illustrates Cases (c) and (b) in Algorithm BIN1. The sandwich condition guarantees that $t_q[i,n] \in [\ell _q, u_q]$, the crosshatched region in (i). BIN1 tests whether ${\bar{R}}_{i m} \ge {\bar{M}}^{q-1}_{(m +1) n}$ and halves the crosshatched region, recursing to the left or right appropriately. The recursion terminates when ${\bar{t}} = t_q[i,n] = \ell _q = u_q$. These are subfigures (ii) and (iii). In (ii) ${\bar{R}}_{i {\bar{t}} } \ge M^{q-1}_{({\bar{t}} +1) n}$ while in (iii) ${\bar{R}}_{i {\bar{t}} } < M^{q-1}_{({\bar{t}} +1) n}$. BIN1 returns the minimum of ${\bar{R}}_{i {\bar{t}} }$ and $M^{q-1}_{({\bar{t}} +1) n}$ as in case (b) in the algorithm. Case (a) of BIN1 (not pictured) is the degenerate situation $t_q[i,n] = \ell _q = u_q =i$ which forces ${\bar{R}}_{i {\bar{t}} } = M^{q-1}_{({\bar{t}} +1) n}=0$ and permits terminating the algorithm

Now, let f(n) be the worst case time required to evaluate a single value $R_{i,j}$ (and thus ${\bar{R}}_{i j}$) and $F_q(m)$ be the worst case time BIN1 requires to calculate $M(q: i, \ell _q, u_q)$ when $u_q - \ell _q < m$. Working through the code yields

$$\begin{aligned} F_q(m) \le \left\{ \begin{array}{ll} 2f(n) + O(1) &{}\ \text{ if } \, q=2, \, m=1 \\ F_2\Bigl (\lceil m/2 \rceil \Bigr ) + 2f(n) + O(1) &{}\ \text{ if } \, q=2, \, m>1 \\ F_{q-1}(n) + f(n) + O(1) &{}\ \text{ if } \, q>2, \, m=1 \\ F_{q}\Bigl (\lceil m/2\rceil \Bigr ) + F_{q-1}(n) + f(n) + O(1) &{}\ \text{ if } \, q>2, \, m>1 \\ \end{array}\right. \end{aligned}$$

This is a very standard multi-dimensional divide-and-conquer recurrence (see, e.g., [6]) which evaluates out to $F_q(n) = O(f(n) \log ^{k-1} n)$. Plugging in Lemma 21 immediately proves

Theorem 5

$$\begin{aligned} \min _{\{{\hat{P}},{\hat{Y}}\}} R_{\max }(\{{\hat{P}},{\hat{Y}}\}) = M^k_{0 n} \end{aligned}$$

can be calculated in $O(n^2 k^2 \log ^{k+1} n)$ time.

For fixed k, this is better than the $O(n^3 \log n)$ algorithm from Theorem 1 and would be the best algorithm known for fixed $k >2$.

Fig. 8

BIN2.2—the second iterated binary search algorithm, specialized for the case $k=2$. When $k=2$, $q=2$ and $i \equiv 0$, so the call $M(q: i, \ell _q, u_q)$ from BIN1 can be rewritten as $T(\ell , u )$. Also note that $M^{q-1}_{(t+1) n} = {\bar{R}}_{(t+1) n}$. The ${\bar{R}}_{i j}$ calls in the algorithm can be simulated by $R'_{i j}$ calls as noted in the comments and explained further in the text

6.3 An Improved Binary Search Algorithm for $k=2$

Lemma 21 permits constructing the $R'_{i j}$ in $O(n k^2 \log ^2 n)$ time instead of the $O(n^2 k^2 \log ^2 n)$ required for $R_{i j}$. This suggests replacing the ${\bar{R}}_{i j}$ calls in BIN1 with $R'_{i j}$ calls. The difficulty with this approach is that Algorithm BIN1 strongly used the monotonicity of $M^q_{i j}$ which was a consequence of the monotonicity of the ${\bar{R}}_{i j}$ derived in Lemma 9. Unfortunately, as noted after the statement of Corollary 1, Lemma 9 can not be generalized to prove the monotonicity of the $R'_{i j}$. Consequentially, the algorithm can not just simply replace the $R_{i j}$ with $R'_{i j}$.

It can, though, use the relationship between $R_{i j}$ and $R'_{i j}$ in Lemma 6 to simulate${\bar{R}}_{i j}$ calls in BIN1 with $R'_{i j}$ calls.

This will be quite technical so, to provide intuition, we first work through the details for $k=2$. When $k=2$, BIN1 only calls case 1 (with $q=2$) and all calls have $i \equiv 0$. This specialized version is written as BIN2.2 in Fig. 8; for simplification, the call $M(2: 0, \ell _q, u_q)$ is relabelled as $T(\ell , u)$. We now show how BIN2.2’s use of ${\bar{R}}_{i j}$ terms can be replaced by $R'_{i j}$ terms.

For given t, define the partitions

$$\begin{aligned} {\hat{P}}(t) \,{:=}\, \{P_1(t),P_2(t)\} \quad \text{ where } \quad P_1(t)\,{:=}\, P_{0t} \ \text{ and } \ P_2(t) \,{:=}\, P_{(t+1) n} \end{aligned}$$

and set

$$\begin{aligned} V(t) \,{:=}\, \max \{R'_{0 t}, R'_{(t+1) n}\}. \end{aligned}$$

From Lemmas 2 and 6

$$\begin{aligned} V(t) = \max \{{\bar{R}}_{0 t},{\bar{R}}_{(t+1) n}\}. \end{aligned}$$

Furthermore, if $V(t) =0$ for any t, then $M^2_{0,n} =0$ and the algorithm can terminate.

Lemma 6 also implies that if $V(t) > 0$, then $d'({\hat{P}}(t)) = {\bar{d}}({\hat{P}}(t))$ and there are only two possibilities

• $d'({\hat{P}}(t)) = {\bar{d}}({\hat{P}}(t)) =1$. Then

  $$\begin{aligned} R'_{0 t} \ge R'_{(t+1) n} \quad \text{ and } \quad {\bar{R}}_{0 t} \ge {\bar{R}}_{(t+1) n} \quad \text{ and } \quad R'_{0 t} = {\bar{R}}_{0 t}. \end{aligned}$$

• $d'({\hat{P}}(t)) = {\bar{d}}({\hat{P}}(t)) =2$. Then

  $$\begin{aligned} R'_{0 t}< R'_{(t+1) n} \quad \text{ and } \quad {\bar{R}}_{0 t} < {\bar{R}}_{(t+1) n}\quad \text{ and } \quad R'_{(t+1) n} = {\bar{R}}_{(t+1) n}. \end{aligned}$$

Now consider the 3 parts of BIN2.2

• (a) If $\ell = \mathbf{u} = \mathbf{0}:$ Then $t_2[0,n]= \ell =0$

  In this case, exactly as in BIN1, $0 = {\bar{R}}_{0 0} \ge {\bar{R}}_{1,n}$ so $M^2_{0 n} =0$.

• (b) If $\ell = \mathbf{u} \not =\mathbf{0}:$ Then $t_2[0,n]=\ell > 0$.

  As in BIN1, the algorithm needs to return $M^{2}_{0 n} = \min \{{\bar{R}}_{0\ell }, {\bar{R}}_{\ell n}\}$.

  By the definition of $t_2[0,n]$

  • $d({\hat{P}}(\ell )) = 1$, so $V(\ell ) = {\bar{R}}_{0 \ell } = R'_{0 \ell }$,

  • $d({\hat{P}}(\ell -1))=2$, so $V(\ell -1) ={\bar{R}}_{\ell n } = R'_{\ell n }$.

  Thus BIN2.2 correctly returns the value

  $$\begin{aligned} \min \{{\bar{R}}_{0 \ell }, {\bar{R}}_{\ell n}\} = \min \{ V(\ell ), V(\ell -1)\} = \min \{R'_{0\ell }, R'_{\ell n}\}. \end{aligned}$$

• (c) If $\ell < \mathbf{u}:$ Then set $m = \lfloor (\ell + u /2\rfloor$. Check if ${\bar{R}}_{0 m} \ge {\bar{R}}_{(m +1) n}$. Start by calculating $V(m) = \max \{R'_{0 t}, R'_{(t+1) n}\}$ and $d'({\hat{P}}(t))$. From the observations above, if $V(m)=0$, then $M^2_{0,n} =0$ and the algorithm can terminate. Otherwise $V(m)\not =0$ and

  $$\begin{aligned} {\bar{R}}_{0 m} \ge {\bar{R}}_{(m +1) n} \quad \hbox {iff} \quad d'({\hat{P}}(m))=1 \quad \hbox {iff} \quad R'_{0 m} \ge R'_{(m +1) n} \end{aligned}$$

  Thus (c) can be implemented properly by just checking whether or not $R'_{0 m} \ge R'_{(m +1) n}$.

Notice that all evaluations of $R_{i j}$ are now simulated by evaluations of $R'_{i j}$. Since Lemma 21 permits constructing the pair $R'_{0 t}$, $R'_{(t +1) n}$ in $O(n k^2 \log ^2 n)$ time this proves

Theorem 6

If $k=2$ then

$$\begin{aligned} \min _{\{{\hat{P}},{\hat{Y}}\}} R_{\max }(\{{\hat{P}},{\hat{Y}}\}) = M^2_{0 n} \end{aligned}$$

can be calculated in $O(n \log ^3 n)$ time.

6.4 An Improved Binary Search Algorithm for General k

Generalizing the ideas above for $k >2$ is more complicated. It will need to utilize information that BIN1 ignored. More specifically, $M(q: i,\ell _q,u_q)$ was evaluated at the end of a recursive chain of calls that actually defined a splitting of $[x_0,x_{i-1}]$ into $k-q$ partitions. The new algorithm will recall and use those partitions. This will be done by passing a list ${{\mathcal {L}}}$ of the right boundaries of the partitions to the called procedure.

Also, BIN1 evaluated ${\bar{R}}_{i j}$ values exactly when they were needed. The new algorithm will defer evaluating $R'_{i j}$ values until a full ${\hat{P}}$ with k partitions has been formed and will then evaluate all of the $R'_{i j}$ values for that ${\hat{P}}$ simultaneously.

Definition 15

For $v < k$ and a sequence $0 \le r_1< r_2< r_3<\cdots<r_v < n$ set (See Fig. 9)

$$\begin{aligned} {{\mathcal {L}}} \,{:=}\, <r_1, r_2,\ldots , r_{v}>. \end{aligned}$$

Such a list will be called a partition sequence with size$|{{\mathcal {L}}}| \,{:=}\, v$. If ${{\mathcal {L}}} = \emptyset$, set $v \,{:=}\, 0$.

Given a partition sequence ${\mathcal {L}}$ of size v,

• Set $l_1\,{:=}\, 0$ and, for $1 \le j \le v$, set $l_{j+1} \,{:=}\, r_{j} +1$.

• If $v=0$, set $V({{\mathcal {L}}}) \,{:=}\, 0$ and leave $d({{\mathcal {L}}})$ undefined. Otherwise, set

  $$\begin{aligned} V({{\mathcal {L}}}) \,{:=}\, \max _{1 \le j \le v} {\bar{R}}_{l_j r_j},\quad d({{\mathcal {L}}}) \,{:=}\, \mathop {\mathrm{arg~max}}\limits _{1 \le j \le v} {\bar{R}}_{l_j r_j}. \end{aligned}$$

• If $v =k-1$, set $r_n \,{:=}\, n$ and $\forall j$, $P_j \,{:=}\, [x_{l_j}, x_{r_j}]$. Define ${{\hat{P}}}({{\mathcal {L}}})$ as

  $$\begin{aligned} {{\hat{P}}}({{\mathcal {L}}}) \,{:=}\, \{P_1,P_2,\ldots ,P_k\}. \end{aligned}$$

• If $v < k-1$ and $r_v< j < n$ define the j-extension of${\mathcal {L}}$ as

  $$\begin{aligned} {{\mathcal {L}}} \oplus j \,{:=}\, <r_1, r_2,\ldots , r_{v}, j>. \end{aligned}$$

Fig. 9

In the diagram above ${\bar{t}} = t_q[i,n]$. This diagram illustrates the recursive calls in Case 2(b) (subfigures (ii) and (iii)) and Case 2(c) (subfigure (i)) in the revised algorithm that calculates $T(v: {{\mathcal {L}}}, \ell _q, u_q)$. ${{\mathcal {L}}} = <r_1, r_2,\ldots , r_{v}>$, $q= k-v$ and $l_{i+1} = r_i +1$. Note that ${\mathcal {L}}$ defines the partitions to the left of $x_{r_v}$. The algorithm works almost the same as BIN1 in trying to find the minimum value of $M^q_{l_{v+1} n}$. The main difference between this algorithm and BIN1 is that if this algorithm ever finds that $V({{\mathcal {L}}}) = \max _{0 \le j \le v} {\bar{R}}_{l_j,r_j} > M^q_{l_{v+1} n}$ the procedure returns immediately

Evaluations of ${\bar{R}}_{l_i r_i}$ will be deferred until $v=k-1$ when ${{\mathcal {L}}}$ will correspond to a full partition. At this point, the evaluation of all of the ${\bar{R}}_{l_i r_i}$ in ${{\hat{P}}}({{\mathcal {L}}})$ will be replaced by evaluation of the $R'_{i j}$ in ${{\hat{P}}}({{\mathcal {L}}})$ using the following:

Lemma 23

For partition sequence ${{\mathcal {L}} } = <r_1, r_2,\ldots , r_{k-1}>$, let $Test({{\mathcal {L}}})$ be the procedure that returns the pair (d, V) where

$$\begin{aligned} V \,{:=}\, \max _{1\le j \le k} {\bar{R}}_{l_j r_j} \quad \text{ and }\quad d \,{:=}\, \min \left\{ j \,:\, {\bar{R}}_{l_j r_j} = V\right\} = {\bar{d}} ({{\hat{P}}}({{\mathcal {L}}})). \end{aligned}$$

Then

• 1. $Test({{\mathcal {L}}})$ can be implemented in $O(n k^2 \log ^2 n)$ time.

• 2. If $V=0$, then $R_{\max }^k (P)=0$.

• 3. If $V > 0$, then $\forall j< d, \, {\bar{R}}_{l_j r_j}< {\bar{R}}_{l_d r_d}$ and $\forall j > d, \, {\bar{R}}_{l_j r_j}\le {\bar{R}}_{l_d r_d}$.

Proof

From Lemma 21 a fixed $R'_{l_j r_j}$ can be constructed in in $O( |r_j-l_j+1| k^2 \log ^2 n)$ time. Since $\sum _{j=1}^k |r_j-l_j+1| = O(n)$, all of the $R'_{l_j r_j}$ in ${{\hat{P}}}({{\mathcal {L}}})$ can be constructed in $O(n k^2 \log ^2 n)$ total time. The remainder of the lemma follows directly from Lemmas 6 and 7 and in particular the facts that

• (i)
  $$\begin{aligned} \ V({{\mathcal {L}}}) = \max _{1 \le j \le k} {\bar{R}}_{l_j r_j} = \max _{1 \le j \le k} R'_{l_j r_j}, \end{aligned}$$

  (45)

• (ii) if $V=0$ then $R_{\max }^k (P)=0$, and

• (iii) if $V\not =0$ then $d'({{\hat{P}}}({{\mathcal {L}}})) = {\bar{d}}({{\hat{P}}}({{\mathcal {L}}}))$. $\square$

We can now describe the algorithm. For ${{\mathcal {L}} } = <r_1, r_2,\ldots , r_v>$ set $q = k - v$ and define

$$\begin{aligned} T(v: {{\mathcal {L}}}, \ell _q, u_q) \,{:=}\, (d,V) \end{aligned}$$

such that

$$\begin{aligned} \begin{aligned} V&\,{:=}\, \max \left\{ V({{\mathcal {L}}}) , \min _{\ell _q \le t \le u_q}\max \left\{ {\bar{R}}_{l_{v+1} t},\, M^{q-1}_{(t+1) n}\right\} \right\} , \\ d&\,{:=}\, \left\{ \begin{array}{ll} \min \left\{ j\,:\, 1 \le j \le v \text{ such } \text{ that } {\bar{R}}_{l_j r_j} = V({{\mathcal {L}}}) \right\} &{} \text{ if } \, V = V({{\mathcal {L}}}),\\ v+1 &{} \text{ if } \, V > V({{\mathcal {L}}}). \end{array} \right. \end{aligned} \end{aligned}$$

(46)

Intuitively, ${\mathcal {L}}$ fixes the first (leftmost) v partitions. The maximum is taken over those v partitions and the best case for the remaining $q=k-v$ partitions on the right. If the maximum is one of the first v partitions, d will record its location. Otherwise, $d=v+1$ denotes that the maximum is not one of them.

We now modify algorithm BIN1 from Fig. 6 so that it calculates $T(v: {{\mathcal {L}}}, \ell _q, u_q)$ instead of $M(q: i, \ell _q, u_q)$. As defined, $M(q: i, \ell _q, u_q)$ didn’t originally store information as to the partition boundaries to the left of location $x_i$. $T(v: {{\mathcal {L}}}, \ell _q, u_q)$ will use that missing information, encoded in ${\mathcal {L}}$. Similar to the previous section we define

Definition 16

The parameters of $T(v: {{\mathcal {L}}}, \ell _q, u_q)$ satisfy the sandwich condition if $\ell _q \le t_q[l_{v+1},n] \le u_q$.

If they satisfy the sandwich condition then

$$\begin{aligned} \min _{\ell _q \le t \le u_q} \max \left\{ R_{l_{v+1} t},\, M^{q-1}_{(t+1) n}\right\} = \min \left\{ R_{l_{v+1} t_q[l_{v+1},n]}, M^{q-1}_{t_q[l_{v+1},n] n} \right\} = M^q_{l_{r+1}n}. \end{aligned}$$

Thus

Property 7

If the parameters of $T(v: {{\mathcal {L}}}, \ell _q, u_q)$ satisfy the sandwich condition then $(d,V) = T(v: {{\mathcal {L}}}, \ell _q, u_q)$ satisfies

$$\begin{aligned} V = \max \left\{ V({{\mathcal {L}}}) , M^q_{l_{v+1}n} \right\} . \end{aligned}$$

(47)

Furthermore, if $V =V({{\mathcal {L}}})$ then $d = d({{\mathcal {L}}})$.

Note that since $j+1\le t_q [j+1,n] < n$, it follows that

Property 8

A call of the form $T(v: {{\mathcal {L}}} \oplus j, j+1, n-1)$ satisfies the sandwich condition.

As a special case, $T(0 : \emptyset , 0, n-1)$ satisfies the sandwich condition so $(d,V) =T(0 : \emptyset , 0, n-1)$ yields $\max \left\{ V(\emptyset ) , M^q_{ l_1 n}\right\} = M^q_{ 0 n}$, which is what is required.

The final main observation is that if $T(v : {{\mathcal {L}}}, \ell _q, u_q)$ is called with $v =|{{\mathcal {L}}}|= k-2$ then ${{\mathcal {L}}} \oplus j$ will define a full partition so $Test({{\mathcal {L}}} \oplus j)$ is well-defined.

We now work through the new algorithm, BIN2. We will always assume that no call $(d,V)=Test({{\mathcal {L}}})$ will ever return $V=0$ because, if it does, Lemma  permits terminating BIN2 and reporting that $M^k_{0,n}=0$.

BIN2 follows. We stress that the logic of BIN2 is exactly the same as that of BIN1 and therefore do not explicitly prove correctness. Instead we describe how the ${\bar{R}}_{i,j}$ evaluations in BIN1 are correctly simulated by the $Test(*: *,*,*)$ calls in BIN2. In particular, boxes labelled “Call” are calls to either Test or recursive calls made by the procedure; boxes labelled Return(d, v) are what the procedure returns (based on the calls it made).

${(1) \, \mathbf{v}=\mathbf{k}-\mathbf{2} \, \hbox {which implies} \, \mathbf{q}= \mathbf{k} - \mathbf{v}=\mathbf{2}: \, \hbox {Recall} \, l_{k-1} = r_{k-2} +1}$

(a) If $\ell _\mathbf{2} =\mathbf{u}_\mathbf{2}= \mathbf{l}_\mathbf{k-1}$ the same analysis as in Sect. 6.2 shows that $t_2[l_{k-1},n] = \ell _2$ so $M^{2}_{l_{k-1} n} = 0$.

Let $(d,V) \,{:=}\, Test({{\mathcal {L}}} \oplus \ell _2)$. If $V \not =0$ then from Property 7, $V = V({{\mathcal {L}}})$ and $d = d({{\mathcal {L}}})$. Thus the following returns the correct answer:

(b) If $\ell _\mathbf{2} = \mathbf{u}_\mathbf{2}\not =\mathbf{l}_\mathbf{k-1}:$ From the sandwich condition, $\ell _2 = t_2[l_{k-1},n]$. To simplify the analysis set

$$\begin{aligned} A \,{:=}\, {\bar{R}}_{l_{k-1} \ell _2 },\ \ B \,{:=}\, {\bar{R}}_{(\ell _2+1) n}, \quad A ' \,{:=}\, {\bar{R}}_{l_{k-1} (\ell _2 -1)},\ \ B' \,{:=}\, {\bar{R}}_{\ell _2 n}, \end{aligned}$$

From the definition of $t_2[l_{k-1},n]$, $A \ge B$, $A' < B'$, and

$$\begin{aligned} M^{2}_{l_{k-1} n} = \min \left\{ \max \{A,B\},\, \max \{A',B'\} \right\} = \min \{A,B'\}. \end{aligned}$$

Now

Recall that

$$\begin{aligned} V({{\mathcal {L}}}) = \max _{1 \le j \le k-2 } {\bar{R}}_{l_j r_j}. \end{aligned}$$

From the facts above and Property 7

$$\begin{aligned} V_A= & {} \max \left\{ V({{\mathcal {L}}}), A, B \right\} =\max \left\{ V({{\mathcal {L}}}), A\right\} , \\ V_B= & {} \max \left\{ V({{\mathcal {L}}}), A', B' \right\} =\max \left\{ V({{\mathcal {L}}}), B' \right\} , \\ V= & {} \max \left\{ V({{\mathcal {L}}}) , M^2_{l_{k-1}n} \right\} = \max \left\{ V({{\mathcal {L}}}), \min \{A,B'\} \right\} . \end{aligned}$$

The following flow directly from the definitions

This provides enough information to calculate $(d,V) = T(k-2 : {{\mathcal {L}}}, \ell _2, \ell _2)$ from the results of the Test() procedures. There are four possibilities.

(c) $\ell _\mathbf{2} < \mathbf{u}_\mathbf{2}:$

Note that by the sandwich condition $\ell _2 \le t_2[l_{k-1},n] \le u_2$, so Eq. 47 implies that $V = \max \left\{ V({{\mathcal {L}}}) , M^2_{l_{k-1}n} \right\} .$ Set $m \,{:=}\, \lfloor (\ell _2 + u_2)/2\rfloor$ and run

By definition, $V' = \max \{ V({{\mathcal {L}}}), A, B \}$ where

$$\begin{aligned} A \,{:=}\, {\bar{R}}_{l_{k-1} m} \quad \text{ and } \quad B \,{:=}\, {\bar{R}}_{(m+1) n}. \end{aligned}$$

Furthermore,

$$\begin{aligned} M^2_{l_{k-1} n} = \min _{l_{k-1} \le t < n} \max \left\{ {\bar{R}}_{l_{k-1} t}, {\bar{R}}_{(t+1) n}\right\} \le \max \{A,B\}. \end{aligned}$$

Note that if $d' \le k-2$ then

$$\begin{aligned} V({{\mathcal {L}}}) = V' \ge \max \{A,B\} \ge M^2_{l_{k-1} n} \end{aligned}$$

and thus $(d,V) = (d',V')$.

If $d' > k-2$ the result of the Test() procedure can not calculate V from $V'$. Similar to BIN1, though, it can halve the possible range of $t_2[l_{k-1},n]$. More specifically,

• If $d'=k-1$

  • ${\bar{R}}_{l_{k-1} m}= A = V' \ge B = {\bar{R}}_{(m+1) n}$

  • $\Rightarrow \ell _2 \le t_2[\ell _{k-1},n] \le m$

  • $\Rightarrow (d,V) = T(k-2 : {{\mathcal {L}}}, \ell _2, m)$.

• If $d' = k$

  • ${\bar{R}}_{(m+1) n} = B = V' > A = {\bar{R}}_{l_{k-1} m}$

  • $\Rightarrow m+1 \le t_2[\ell _{k-1},n] \le u_2$

  • $\Rightarrow (d,V) = T(k-2 : {{\mathcal {L}}}, m+1 , u_2)$.

This provides enough information to calculate $(d,V) \,{:=}\, T(k-2 : {{\mathcal {L}}}, \ell _2, u_2)$ from the results of the Test() procedure. There are three possibilities.

${(2) \, \mathbf{v}< \mathbf{k}-2: \, \hbox {which implies} \, \mathbf{q}= \mathbf{k} - \mathbf{v}: \, \hbox {Recall} \, l_{v+1} = r_{v} +1}$

(a) If $\ell _\mathbf{q} = \mathbf{u}_\mathbf{q} = \mathbf{l}_\mathbf{v+1}$ the same analysis as in Sect. 6.2 shows that $\ell _q = t_q[l_{v+1},n]$ so

$$\begin{aligned} 0 \ge {\bar{R}}_{l_{v+1},l_{v+1}} \ge M^{q-1}_{(l_{v+1}+1) n}\ge 0 \end{aligned}$$

(48)

which immediately implies that $M^{q}_{(l_{v+1}+1) n} = 0$ and so, from Property 7,

(b) If $\ell _\mathbf{q} = \mathbf{u}_\mathbf{q}\not =\mathbf{l}_\mathbf{v+1}:$ From the sandwich condition, $\ell _q = t_q[l_{v+1},n]$. Set

$$\begin{aligned} A \,{:=}\, {\bar{R}}_{l_{v+1} \ell _q },\, B \,{:=}\, M^{q-1}_{(\ell _q+1) n}, \quad A '\,{:=}\, {\bar{R}}_{l_{v+1} (\ell _q -1)},\, B' \,{:=}\, M^{q-1}_{\ell _q n}, \end{aligned}$$

Again from the definition of $t_q[l_{v+1},n]$, $A \ge B$, $A' < B'$, and $M^{q}_{l_{r+1} n} = \min \{A,B'\}$. Now

Similar to the $v=k+2$ case, from the facts above and the definition of T(),

$$\begin{aligned} V_A= & {} \max \left\{ V({{\mathcal {L}}}), A, B \right\} =\max \left\{ V({{\mathcal {L}}}), A \right\} \\ V_B= & {} \max \left\{ V({{\mathcal {L}}}), A', B' \right\} =\max \left\{ V({{\mathcal {L}}}), B' \right\} \end{aligned}$$

The pertinent facts are

$$\begin{aligned} \begin{array}{lclclcl} A \ge B &{} \text{ so } &{} d_A \not = v+2, &{} &{} A' < B' &{} \text{ so } &{} d_B \not = v+1,\\ \text{ if } d_A \le v &{} \Rightarrow &{} V_A = V({{\mathcal {L}}}) \ge A &{} &{} \text{ if } d_B \le v &{}\Rightarrow &{} V_B = V({{\mathcal {L}}}) \ge B',\\ \text{ if } d_A=v+1 &{} \Rightarrow &{} V_A =A> V({{\mathcal {L}}}), &{} &{} \text{ if } d_B = v+2 &{}\Rightarrow &{} V_B = B' > V({{\mathcal {L}}}). \end{array} \end{aligned}$$

This provides enough information to calculate $(d,V) = T(v : {{\mathcal {L}}}, \ell _q, \ell _q)$ from the results of the two recursive calls. There are four possibilities.

(c) $\ell _\mathbf{q} < \mathbf{u}_\mathbf{q}:$ From property 7, $V = \max \left\{ V({{\mathcal {L}}}) ,\, M^{q}_{l_{r+1}n} \right\} .$

Now set $m \,{:=}\, \lfloor (\ell _q + u_q)/2\rfloor$ and run

By definition, $V' = \max \{ V({{\mathcal {L}}}), A, B \}$ where

$$\begin{aligned} A \,{:=}\, {\bar{R}}_{l_{v+1} m} \quad \text{ and } \quad B \,{:=}\, M^{q-1}_{(m+1) n}. \end{aligned}$$

Furthermore,

$$\begin{aligned} M^q_{l_{v+1} n} = \min _{l_{v+1} \le t \le n} \max \left\{ {\bar{R}}_{l_{v+1} t}, M^{q-1}_{(t+1) n}\right\} \le \max \{A,B\}. \end{aligned}$$

Now note that if $d' \le v$ then

$$\begin{aligned} V({{\mathcal {L}}}) = V' \ge \max \{A,B\} \ge M^q_{l_{v+!} n} \end{aligned}$$

and thus $(d,V) = (d',V')$.

If $d' > v$ we can not know V from $V'$, but again, can halve the possible range of $t_q[l_{v+1},n]$. More specifically

• If $d=v+1$

  • ${\bar{R}}_{l_{v+1} m}= A = V' \ge B = M^{q-1}_{(m+1) n}$

  • $\Rightarrow \ell _q \le t_q[\ell _{v+1},n] \le u_q$

  • $\Rightarrow (d,V) = T(v: {{\mathcal {L}}}, \ell _q, m)$.

• If $d = v+2$

  • $M^{q-1}_{(m+1) n} = B = V' > A = {\bar{R}}_{l_{v+1} m}$

  • $\Rightarrow m+1< t_q[\ell _{v+1},n] < n$

  • $\Rightarrow (d,V) = T(v : {{\mathcal {L}}}, m+1 , u_q)$.

This provides enough information to calculate $(d,V) = T(v : {{\mathcal {L}}}, \ell _q, \ell _q)$ from the results of the recursive call. There are three possibilities.

By construction, when the algorithm terminates, it returns the correct answer. The running time analysis is very similar to that of BIN1.

Let g(n) denote the time to run one Test() procedure. From Lemma 23, $g(n) =O(n k^2 \log ^2 n)$. Now set $G_q(m)$ be the worst case time required to calculate $T(v: {{\mathcal {L}}}, \ell _q , u_q)$ when $u_q - \ell _q < m$ and $v = k-q$. Working through the code gives

$$\begin{aligned} G_q(m) \le \left\{ \begin{array}{ll} 2g(n) &{}\ \text{ if } \, q=2, \, m=1 \\ G_2(\lceil m/2 \rceil ) + g(n) &{}\ \text{ if } \, q=2, \, m>1 \\ 2G_{q-1}(n) &{}\ \text{ if } \, q>2, \, m=1 \\ G_{q}(\lceil m/2\rceil ) +2G_{q-1}(n) &{}\ \text{ if } \, q>2, \, m>1\\ \end{array} \right. \end{aligned}$$

which evaluates out to $G_q(n) = O(g(n) \log ^{k-1} n) = O(n k^2 \log ^{k+1} n)$.

We have therefore just proven

Theorem 7

For any k, the minmax regret k-sink evacuation time

$$\begin{aligned} \min _{\{{\hat{P}},{\hat{Y}}\}} R_{\max }(\{{\hat{P}},{\hat{Y}}\}) = M^k_{0 n} \end{aligned}$$

can be calculated in $O\left( n k^2 \log ^{k+1} n\right)$ time.

7 Conclusion and Further Directions

In this paper we derived new combinatorial properties that permitted efficiently solving the minmax regret k-sink location problem for dynamic flows on a path with uniform edge capacities. This provided an improved algorithm for the $k=2$ case and the first polynomial time algorithms for the $k > 2$ case.

As noted earlier, our analysis assumed that sinks could be placed anywhere on an edge. An alternative model would restrict sink placement to vertices. We note that our results, algorithms and running times will all still hold in the vertex-on-sink model. To prove this, though, would require revisiting all the proofs and restricting all minimums/maximums over ranges to minimums/maximums over vertices in those ranges. This is mechanical; in many cases, such as the proof of Lemma 20, this would involve finding the edge in which a non-vertex minimum/maximum is found and then returning the minimum/maximum value at one of the endpoints of that edge. In addition, the proof of Lemma 22 explicitly used the $O(n \log n)$ algorithm from [7] to construct ${\varTheta }^k_{\mathrm {opt}}(P,s)$ for fixed scenarios $s \in S^*$. Bhattacharya et al. [7] also assumed that sinks could be anywhere so it would also be necessary to go modify [7]’s algorithm in similar ways as well to work when sinks are restricted to be on vertices.

We conclude by discussing possible extensions. The normal (optimization and not regret) version of the sink location problem is NP-Hard to solve on general graphs even with $k=1$ [24], so attempting to extend the results in this paper to general graphs would not be possible. Chen and Golin [15] gives polynomial time algorithms for placing k sinks on a tree to minimize evacuation time but only the $k=1$ case [9] has been solved for minmax regret with an $O(n \log n)$ algorithm. The bottleneck to solving the k-sink location minmax regret problem on trees is that while there is an understanding of the structure of the worst case scenario set for trees when $k=1$ there is still no good understanding of the structure when $k >1$, i.e., a tree analogue for Theorem 1.

Another extension would be, on paths, to attempt to extend the results to dynamic flows with general capacities on the edges. More specifically, all of the prior work quoted in Sect. 1 assumes uniform capacity, i.e., every edge having identical capacity. A more natural problem formulation that appears in realistic dynamic flow problems allows different edges to have different capacities. Currently, though, there still is no polynomial time solution for solving the minmax regret problem on a dynamic path with general edge capacities, even when $k=1$. Similar to the uniform capacity tree problem just discussed, the bottleneck in finding a solution seems to be that, for different capacity edges on a path, even when $k=1$, there is no understanding of the combinatorial structure of the set of worst-case scenarios.

Appendices

Appendix

The Critical Vertex Tree Data Structure

In this section we describe the CVT Data Structure of [9] and how it can be used to implement the operations described in Lemma 11 in $O(\log n)$ time.

Let s be any fixed scenario. We start with [9]’s O(n) time construction (slightly modified) of an O(n) space CVT for a fixed s and afterwards describe how this can be further modified, to construct in O(n) time an extended CVT that permits queries to any $s \in S^*$.

Assume that $n+1$ is a power of 2. If not, pad path P with empty vertices on the right (with no weights) to reach a power of 2. Also before starting, perform a O(n) preprocessing step, calculating and storing all of the values $W^s_i = \sum _{j=0}^i w_{j}(s)$. After this step, for any $a \le b$, the values $W^s_{ a, b} = \sum _{j=a}^b w_{j}(s)$ can be calculated in O(1) time. Note that, given⁵$x < y$, the values

$$\begin{aligned} W^s(x,y) = \sum _{x \le x_j \le y} w_j(s)= W^s_b - W^s_{a-1} \end{aligned}$$

can then also be calculated in O(1) time.

Recall that ${\varTheta }_{L}(P,x,s)$ and ${\varTheta }_{R}(P,x,s)$ were defined to be the time needed to evacuate everything to the left (resp. right) of sink x to x under scenario s. Then, from Eq. 1,

$$\begin{aligned} {\varTheta }_{L}([x',x],x,s)]=\max _{ x' \le x_i < x\,:\, W^s(x',x_i) > 0 } \left\{ (x-x_{i})\tau +\frac{W^s(x',x_i)}{c} \right\} . \end{aligned}$$

(49)

Similarly, set

$$\begin{aligned} {\varTheta }_{R}([x',x],x',s) = \max _{ x' < x_i \le x \,:\,W^s(x_i,x')>0} \left\{ (x_{i}-x')\tau +\frac{W^s(x_i,x')}{c} \right\} . \end{aligned}$$

(50)

Definition 17

The left/right critical vertices of $([x',x],s)$ are

$$\begin{aligned} C_{L}([x',x],s)&\,{:=}\,&\mathop {\mathrm{arg~max}}\limits _{ i\,:\, x' \le x_i< x\,:\, W^s(x',x_i)>0} \left\{ (x-x_{i})\tau +\frac{W^s(x',x_i)}{c} \right\} ,\\ C_{R}([x',x],s)&\,{:=}\,&\mathop {\mathrm{arg~max}}\limits _{ i\,:\, x' < x_i \le x\,:\, W^s(x_i,x)> 0} \left\{ (x_{i}-x)\tau +\frac{W^s(x_i,x)}{c} \right\} . \end{aligned}$$

Fig. 10

The left critical-vertex of path $[x',x]$ is the node m at which the top equation in Definition 17 is maximized. Intuitively, this is the last vertex at which the first supply from $x'$ has to stop due to congestion when evacuating to x. The diagram illustrates two paths $[x',x]$ and $[x,x'']$ and their respective critical vertices $m,m'$. The main fact upon which the CVT is based is that the critical vertex of combined path $[x',x'']$ must be one of m and $m'$

Intuitively, the critical vertex is the last location at which items starting on the leftmost (rightmost) vertex encounter congestion. Note that if the critical vertices of $[x',x]$ are known, then ${\varTheta }_{L}([x',x],x,s)$ and ${\varTheta }_{R}([x',x],x's)$ can be calculated in O(1) time. The major observation [9] upon which the CVT data structure is based is (Fig. 10) that if $x' \le x \le x''$ then the left (right) critical vertex of $[x',x'']$ is either (i) the left (right) critical vertex of $[x',x]$ or (ii) the left (right) critical vertex of $[x,x'']$. Thus the critical vertices of $([x',x''],s)$ can be found in O(1) time from the critical vertices of its two subpaths.

The data structure will require a slightly extended version of this.

Lemma 24

Let $i \le j \le k$. The critical vertices of $(P_{i k},s)$ can be constructed in O(1) time from the critical vertices of $(P_{i j},s)$ and $(P_{(j+1) k},s)$.

Proof

First note that because $(P_{j (j+1)},s)$ only contains two vertices, its critical vertices can be found in O(1) time.

The critical vertices of $(P_{i (j+1)},s)$ can be calculated in O(1) time from those of $(P_{i j},s)$ and $(P_{j (j+1)},s)$. The critical vertices of $(P_{i k},s)$ can be calculated from those of $(P_{i (j+1)},s)$ and $(P_{(j+1) k},s)$ in a further O(1) time. $\square$

A critical vertex tree $T^s$ for s was then defined by [9] as follows.

• $T^s$ is a balanced binary tree with the vertices of P as its leaf nodes⁶.

• For a node $u \in T^s$ let L(u) (resp. R(u)) denote the index of the leftmost (rightmost) vertex on P that belongs to the subtree $T^s(u)$ rooted at u. Node $u \in T^s(u)$ corresponds to the subpath $P(u) = \left[ x_{L(u)}, x_{R(u)}\right]$.

• Vertex $u \in T^s$ will store the critical values $C_L(P(u),s)$ and $C_R(P(u),s)$.

A leaf node corresponds to a single vertex path and is thus its own critical vertex. For non-leaf u, let $u_l$ and $u_r$ denote its left and right children. Then $P(u_l) = \left[ x_{L(u_l)},x_{R(u_l)}\right]$ and $P(u_r) = \left[ x_{L(u_r)},x_{R(u_r)}\right]$ where $R(u_l) + 1 = L(u_r)$. Lemma 24 thus permits finding the critical vertices of P(u) from the critical vertices of $P(u_l)$ and $P(u_r)$ in O(1) time. The entire critical vertex tree $T^s$ can therefore be constructed in O(n) time (Fig. 11).

Because $n+1$ is a power of 2, $T^s$ may be stored implicitly in an array so that any node u can be accessed directly in O(1) time. In addition, if u has height h then P(u) has the form $\left[ x_{v 2^h}, x_{(v+1)2^h-1}\right]$ and every path of the form $\left[ x_{v 2^h}, x_{(v+1)2^h-1}\right]$ is P(u) for some u. In particular, for any u this permits evaluating L(u) and R(u) in O(1) time. For $u,u'$, this in turn permits checking in O(1) time whether $P(u) \subset P(u')$, $P(u') \subset P(u)$ or $P(u) \cap P(u') = \emptyset$ (these three are the only possibilities).

Fig. 11

The Critical Vertex Tree $T^s$ for scenario s is a balanced tree with leaf nodes corresponding to path vertices and internal tree nodes corresponding to the subpath spanning descendant leaves. Node u, corresponding to subpath $P(u)=\left[ x_{L(u)}, x_{R(u)}\right]$, will store the locations of the left and right critical vertices of P(u) under scenario s

We now define

Definition 18

Set $s^+$ to be the scenario with $\forall j, w_j(s) = w_j^+$ and $s^-$ to be the scenario with $\forall j, w_j(s) = w_j^-$. The Critical Vertex Tree (CVT) Data Structure is the pair $T^{s^+}$ and $T^{s^-}$ along with $W^{s^+}_i$, $W^{s^-}_i$ for all $i=0,1,\ldots ,n$.

For $t_1 \le t_2$ let $s= s^*_B(t_1,t_2)$ and consider $T^{s}$. Note that all three trees $T^{s^+}$, $T^{s^-}$ and $T^{s}$ have the same topology and only differ in the values stored at the nodes. Let $u^{s^+}$, $u^{s^-}$ and $u^s$ respectively denote the same node u in the three trees. It is straightforward to see that

• 1. If $R(u) < t_1$ or $R(u) > t_2$ then the subtrees rooted at $u^{s^-}$ and $u^s$ are identical (including their critical vertex values). Such nodes $u\in T^s$ are called low nodes.

• 2. If $t_1 \le L(u) \le R(u) \le t_2$ then the subtrees rooted at $u^{s^+}$ and $u^s$ are identical (including their critical vertex values). Such nodes $u \in T^s$ are called high nodes.

• 3. If $u \in T^s$ is neither low nor high it is called a split node. Split nodes must be one of the $O(\log n)$ tree ancestors of $x_{t_1}$ and/or $x_{t_2}$.

Given the CVT Data Structure and $s= s^*_B(t_1,t_2)$ this permits implicitly “constructing” $T^s$ in $O(\log n)$ time as follows. By processing the ancestors of $x_{t_1}$ and $x_{t_2}$ from lowest to highest and using the preprocessed information from the CVT, the critical vertices of the split nodes u can be calculated in O(1) time per node or $O(\log n)$ total time. Since there are at most two such split nodes u’s of a given height, their information can be stored in an array permitting O(1) lookup.

The above gives an implicit construction of $T^s$; the critical vertex information of any node $u\in T^s$ can be retrieved in O(1) time from $T^{s^+}$, $T^{s^-}$ or the split node array by first determining whether it is low, high or split and then looking it up in the appropriate array. Finally, note that $W_i^s$ values can be retrieved from the $W^{s^+}_i$ and $W^{s^-}_i$ values in O(1) time. Thus, given the CVT Data Structure, after the $O(\log n)$ construction of the split-node array, we can assume the existence of the CVT for s. We write this as

Lemma 25

Assume the CVT Data Structure has already been built. Then for any $t_1 \le t_2$ and $s= s^*_B(t_1,t_2)$, $T^s$ can be built in $O(\log n)$ time.

Definition 19

• A node path in P is a subpath of the form $P(u) = \left[ x_{v 2^h}, x_{(v+1)2^h-1}\right]$ where $u \in T^s$.

• Let $i \le j$. A Tree Decomposition of $P_{i j}$ of size t is a sequence $i-1=i_0< i_1< \ldots < i_{t} =j$ such that for $k=1,\ldots ,t$, $P_{(k)} =[x_{i_{k-1}+1}, x_{i_{k}}]$ is a node path. Equivalently, it is a sequence of nodes $u_1,u_2,\ldots ,u_t \in T^s$ such that $P(u_k) = [L(u_k), R(u_k)] = [x_{i_{k-1}+1}, x_{i_{k}}]$.

• A Minimal Tree Decomposition (MTD) of $P_{i j}$ is a tree decomposition of minimal size.

Note that the MTD of $P_{i j}$ is unique and, for each h, contains at most two subpaths of length $2^h$, and thus has size $O(\log n)$. It can also easily be constructed in $O(\log n)$ time. See Fig. 12 for an example.

Fig. 12

The MTD for $P_{i j}$ with $i=29$ and $j = 329$. The path $[x_i, x_j]$ can be decomposed into the sequence 28, 29, 31, 63, 127, 255, 319, 327, 329 which corresponds to the 8 node paths shown above, where the size of each node path is denoted below it

For a given $P_{i j}$ and $s= s^*_B(t_1,t_2)$ let MTD[i, j, s] denote the corresponding MTD of $P_{i j}$ of size $t = O(\log n)$ along with the associated three arrays L[1..t], R[1..t] and $R'[1..t]$ defined as follows: for $1 \le k \le t$, set

$$\begin{aligned} L[k]&\,{:=}\, {\varTheta }_L(P_{i {R(u_k)}}, x_{R(u_k)},s)&\quad&\text{(left } \text{ evacuation } \text{ time } \text{ from } \, x_i \, \text{ to } \, x_{R_{u_k}}\text{) },\\ R[k]&\,{:=}\, {\varTheta }_R(P_{L(u_k),x_j},x_{ L(u_k)},s)&\quad&\text{(right } \text{ evacuation } \text{ time } \text{ from } \, x_j \, \text{ to } \, x_{L_{u_k}}\text{) },\\ R'[k]&\,{:=}\, {\varTheta }_R(P_{i, {R(u_k)}}, x_i,s)&\quad&\text{(right } \text{ evacuation } \text{ time } \text{ from } \, x_{R_{u_k}} \, \text{ to } \, x_i\text{) }. \end{aligned}$$

Given a preconstructed CVT data structure these arrays can be filled in by first building $T^s$ in $O(\log n)$ time using Lemma 25 and then repeated applications of Lemma 24 utilizing the critical vertex values stored at the nodes of $T^s$.

We can now prove Lemma 11.

Proof of Lemma 11

The proof first first proves (1), then (3) and (4) and then returns to prove (2). In what follows, the left and right children of node u will be denoted by $u_l$ and $u_r$. $t=O(\log n)$ will always denote the size of the current MTD.

${\hbox {Lemma}~11 \, (1): \, \hbox {Calculating} \, {\varTheta }_L(P_{i j},x, s) \, \hbox {and} \, {\varTheta }_R(P_{i j},x,s).}$

To calculate ${\varTheta }_L(P_{i j},x, s)$, first binary search in $O(\log n)$ time to find v such that $x_{v-1} < x \le x_v \le x_j$. Next build MTD[i, v, s] in O(t) time. From Lemma 15

$$\begin{aligned} {\varTheta }_L(P_{i j},x, s) = {\varTheta }_L(P_{i v},x, s) - \tau (x_v-x) = L[t] - \tau (x_v-x). \end{aligned}$$

The calculation of ${\varTheta }_R(P_{i j},x,s)$ is similar (and symmetric).

${\hbox {Lemma}~11 \, (3): \, \hbox {Constructing} \, x''=\max \{x' \in [x_i,x_j] \,:\, {\varTheta }_L(P',x',s) \le \alpha \}.}$

First build MTD[i, j, s] in $O(\log n)$ time.

If ${\varTheta }_L(P_{i j} ,x_j,s) = L[t] \le \alpha$ then the answer is just $x''=x_j$. We therefore assume that there exists $v \le j$ such that

$$\begin{aligned} v = \min \left\{ r \,:\, i \le r < j, \text{ and } {\varTheta }_L(P_{i j} ,x_r,s) \ge \alpha \right\} . \end{aligned}$$

Given v, part (1) of the Lemma permits calculating ${\varTheta }_L(P_{i v} ,x_v,s)$ in $O(\log n)$ time. From Lemma 15, for $x' \in (x_{v-1},x_v]$,

$$\begin{aligned} {\varTheta }_L(P_{i j},x',s) = {\varTheta }_L(P_{i v},x',s) = {\varTheta }_L(P_{i v} ,x_v,s) - \tau (x_v-x'). \end{aligned}$$

Thus

$$\begin{aligned} x'' =\left\{ \begin{array}{ll} x_{v-1} &{} \text{ if } {\varTheta }_L(P_{i v} ,x_v,s) - \tau (x_v-x_{v-1}) > \alpha ,\\ \frac{1}{\tau }\left( \alpha - {\varTheta }_L(P_{i v} ,x_v,s) + \tau x_v\right) &{} \text{ otherwise }. \end{array} \right. \end{aligned}$$

and $x''$ can therefore be found in $O(\log n)$ time from v. It remains to show how to find v in $O(\log n)$ time from MTD[i, j, s].

To find v, first use $O(\log n)$ time to find the smallest k such that $L[k] \ge \alpha$.

Use part (1) of the Lemma to check, in $O(\log n)$ time, whether ${\varTheta }_L(P_{i j},x_{L(u_k)}, s) \ge \alpha$. If yes, then because $R(u_{k-1}) = L(u_k) -1$, $v=L(u_k)$ and the process finishes.

Otherwise $x_v \in P(u_k)$. Set $u \,{:=}\, u_k$. We now simulate a binary search for $x_v \in P(u)$ by walking down the subtree of $T^s$ rooted at u, on each level deciding in O(1) time whether to walk left or right. See Fig. 13.

Fig. 13

Illustration of the proof of Lemma 11 (3), trying to find leftmost v satisfying ${\varTheta }_L(P_{i v}, x_{v},s) \ge \alpha$. It is known in advance that $x_v\in P(u)$. Testing whether ${\varTheta }_L(P_{i R(u_l)}, x_{R(u_l)},s) \ge \alpha$ permits determining whether $x_v \in u_l$ or $x_v \in u_r$

To start, set ${\bar{P}} \,{:=}\, P_{i (L(u)-1)}$ and from MTD[i, j, s] construct the left critical vertices of ${\bar{P}}$ in $O(\log n)$ time. We know that

$$\begin{aligned}&(\mathrm{i})\, x_v \in P(u),\quad (\mathrm{ii})\, {\varTheta }_L({\bar{P}} , x_{L(u)-1},s) < \alpha , \nonumber \\&(\mathrm{iii})\, {\varTheta }_L(P_{i R(u)}, x_{R(u)},s) \ge \alpha . \end{aligned}$$

(51)

• 1. If P(u) is one node, then $u =x_v$. Stop.

• 2. Otherwise set ${\bar{P}}' \,{:=}\, P_{i R(u_l)}$, the concatenation of ${\bar{P}}$ and and $P(u_l)$. The left critical vertices of $P(u_l)$ can be extracted from $T^{s}$ in O(1) time. Lemma 24 permits combining them with the known critical vertices of ${\bar{P}}$ to construct the left critical vertices of ${\bar{P}}'$ in O(1) time. This in turn permits the calculation of ${\varTheta }_L({\bar{P}}',x_{R(u_l)},s)$ in O(1) time

• 3. If ${\varTheta }_L({\bar{P}}',x_{R(u_l)},s) < \alpha$, set ${\bar{P}} \,{:=}\, {\bar{P}}'$ and $u= u_r$. Otherwise, keep ${\bar{P}}$ unchanged and set $u\,{:=}\, u_l$.

• 4. Return to step 1

Note that $R(u_l) = L(u_r) -1$ so after step (3), Eq. 51 remains correct for the new value of v, regardless of whether the algorithm walks left or right.

Thus, after $O(\log n)$ decision steps, this procedure reaches a leaf of the tree and this leaf must be $x_v$. Since each step uses only O(1) time and the preceding parts used only $O(\log n)$ time, the total procedure uses $O(\log n)$ time.

${\hbox {Lemma}~11 \, (4): \, \hbox {For} \, x \in [x_i,x_j], \, \hbox {calculate} \, {\bar{j}} = \max \{j' \le j\,:{\varTheta }_R([x,x_{j'}],x,s) \le \alpha \}.}$

First use $O(\log n)$ time to find v such that $x_{v} \le x < x_{v+1}$. From Lemma 15,

$$\begin{aligned} {\varTheta }_R([x,x_{j'}],x,s) = {\varTheta }_R(P_{v j'} ,x_v,s) - \tau (x - x_{v}). \end{aligned}$$

Setting $\alpha ' \,{:=}\, \alpha + \tau (x-x_{v})$, the problem is then equivalent to finding

$$\begin{aligned} \max \{j' \le j\,:{\varTheta }_R(P_{v j'},x_v,s) \le \alpha '\}. \end{aligned}$$

Now build MTD[v, j, s] in $O(\log n)$ time. If $R'[t] \le \alpha$ then ${\bar{j}} = j$ and the process finishes.

Otherwise, in $O(\log n)$ time, find the largest index k such that $R'[k] \le \alpha '$.

Next use Part 1 to check in $O(\log n)$ time if ${\varTheta }_R\left( P_{v (R(u_k)+1)},x_{v},s \right) > \alpha '$.

If yes, then ${\bar{j}} = R(u_k)$. Otherwise $x_{{\bar{j}}} \in u_k$ and can be found in $O(\log n)$ time using essentially the same binary search procedure as in (3).

${\hbox {Lemma}~11 \, (2): \, \hbox {Calculating} \, {\varTheta }^1(P_{i j}, s) \, \hbox {and associated} \, x^* \, \hbox {value}.}$

Let

$$\begin{aligned} v \,{:=}\, \min \Bigl \{ r \,:\, i \le r \le j, \text{ and } {\varTheta }_L(P_{i j},x_v,s) \ge {\varTheta }_R(P_{i j} ,x_v,s) \Bigr \}. \end{aligned}$$

Then $x_{v-1} \le x^* \le x_v$. If v were known we could use the techniques seen previously to calculate both ${\varTheta }_L(P_{i j},x_v,s)$ and ${\varTheta }_R(P_{i j},x_{v-1},s)$ in $O(\log n)$ time and then use Lemma 15 to find $x^*$ and ${\varTheta }^1(P_{i j}, s)$ in a further O(1) time.

Instead of directly finding v, we actually find the smallest ${\bar{v}}$ such that ${\varTheta }_L(P_{i j},x_{{\bar{v}}} ,s) \ge {\varTheta }_R(P_{i j} ,x_{{\bar{v}} +1} ,s)$. Then

$$\begin{aligned} {\varTheta }_L(P_{i j},x_{{\bar{v}} + 1} ,s) >{\varTheta }_L(P_{i j},x_{{\bar{v}}} ,s) \ge {\varTheta }_R(P_{i j} ,x_{{\bar{v}} +1} ,s) \end{aligned}$$

and

$$\begin{aligned} {\varTheta }_L(P_{i j},x_{{\bar{v}} -1} ,s) < {\varTheta }_R(P_{i j} ,x_{{\bar{v}}} ,s) \le {\varTheta }_R(P_{i j} ,x_{{\bar{v}} -1} ,s) \end{aligned}$$

so either $v = {\bar{v}}$ or $v = {\bar{v}}+1$. We can then find the value of v in $O(\log n)$ time using 4 applications of part (1),

To find ${\bar{v}}$, first, in $O(\log n)$ time build MTD[i, j, s]. In $O(\log n)$ time, find the smallest k such that $L[k] \ge R[k+1]$. Let $u= u_k$. This implies that

$$\begin{aligned}&{\varTheta }_L(P_{i j}, x_{R(u)},s) \ge {\varTheta }_R(P_{i j}, x_{R(u)+1},s) \quad \text{ and } \\&{\varTheta }_L(P_{i j}, x_{L(u)-1},s) \ge {\varTheta }_R(P_{i j}, x_{L(u)},s) \end{aligned}$$

Thus ${\bar{v}} \in P(u_k)$. Set $u \,{:=}\, u_k$, $P_L \,{:=}\, P_{i (L(u)-1)}$ and $P_R \,{:=}\, P_{(R(u)+1) j}$. $P_L, P_R,u$ satisfy

$$\begin{aligned} (\mathrm{i})\, {\bar{v}} \in P(u),\quad (\mathrm{ii}) \, P_L = P_{i (L(u)-1)}, \quad (\mathrm{iii})\, P_R = P_{(R(u)+1) j} \end{aligned}$$

(52)

Fig. 14

Illustration of the proof of Lemma 11 (2), trying to find leftmost ${\bar{v}}$ satisfying ${\varTheta }_L(P_{i j},x_{{\bar{v}}} ,s) \ge {\varTheta }_R(P_{i j} ,x_{{\bar{v}} +1} ,s)$. It is known that $x_v \in P(u)$. Comparing ${\varTheta }_L(P_{i j},x_{R(u_l)} ,s)$ and ${\varTheta }_L(P_{i j},x_{L(u_r} ,s)$ permits determining whether $x_{{\bar{v}}} \in P(u_l)$ or $x_{{\bar{v}}} \in P(u_r)$

We again do a simulated binary search for ${\bar{v}}$. To initialize, in $O(\log n)$ time, find the left critical vertex of $P_L$ and the right critical vertex of $P_R$.

At each iterative step we will, in O(1) time, replace u by either $u_l$ or $u_r$ maintaining the correctness of all three invariants in Eq. 52. Since u starts at height $O(\log n)$ this process only uses $O(\log n)$ additional time (Fig. 14).

• 1. If u is a leaf stop and set ${\bar{v}} \,{:=}\, u$.

• 2. Set ${\bar{P}}_L \,{:=}\, P_{i R(u_l)}$ (the concatenation of $P_L$ and $P(u_l)$) and ${\bar{P}}_R \,{:=}\, P_{L(u_r) j}$ (the concatenation of $P(u_r)$ and $P_R$).

• 3. From MTD[i, j, s] find the left critical vertex of $P(u_l)$ and right critical-vertex of $P(u_r)$ for s in O(1) time. Use the known left critical vertex of $P_L$ and right critical vertex of $P_R$ and Lemma 24 to construct the left critical vertex of ${\bar{P}}_L$ and right critical vertex of ${\bar{P}}_R$ in O(1) time. Then calculate ${\varTheta }_L({\bar{P}}_L, x_{R(u_l)},s)$ and ${\varTheta }_R({\bar{P}}_R, x_{L(u_r)},s)$ in O(1) time.

• 4. If ${\varTheta }_L({\bar{P}}_L, x_{R(u_l)},s) \le {\varTheta }_R({\bar{P}}_R, x_{L(u_r)},s)$ set $P_R \,{:=}\, {\bar{P}}_R$ and $u \,{:=}\, u_l$. Otherwise set $P_L \,{:=}\, {\bar{P}}_L$ and $u \,{:=}\, u_r$.

• 5. Go to step 1

$\square$