Minmax Regret 1-Sink Location Problems on Dynamic Flow Path Networks with Parametric Weights

Abstract

This paper addresses the minmax regret 1-sink location problem on dynamic flow path networks with parametric weights. We are given a dynamic flow network consisting of an undirected path with positive edge lengths, positive edge capacities, and nonnegative vertex weights. A path can be considered as a road, an edge length as the distance along the road and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. We consider the problem of locating a sink in the network, to which all the people evacuate from the vertices as quickly as possible. In our model, each weight is represented by a linear function in a common parameter t, and the decision maker who determines the location of a sink does not know the value of t. We formulate the sink location problem under such uncertainty as the minmax regret problem. Given t and a sink location x, the cost of x under t is the sum of arrival times at x for all the people determined by t. The regret for x under t is the gap between the cost of x under t and the optimal cost under t. The task of the problem is formulated as the one to find a sink location that minimizes the maximum regret over all t. For the problem, we propose an $O(n^4 2^{\alpha (n)} \alpha (n) \log n)$ time algorithm where n is the number of vertices in the network and $\alpha (\cdot )$ is the inverse Ackermann function. Also for the special case in which every edge has the same capacity, we show that the complexity can be reduced to $O(n^3 2^{\alpha (n)} \alpha (n) \log n)$.

A full version of the paper is available at [13]; https://arxiv.org/abs/2011.13569.

This work is supported by JSPS KAKENHI Grant-in-Aid for Early-Career Scientists (18K18003, 20K19746), JSPS KAKENHI Grant-in-Aid for Scientific Research (B) (19H04068), and JST CREST (JPMJCR1402).

1 Introduction

Recently, many disasters, such as earthquakes, nuclear plant accidents, volcanic eruptions and flooding, have struck in many parts of the world, and it has been recognized that orderly evacuation planning is urgently needed. A powerful tool for evacuation planning is the dynamic flow model introduced by Ford and Fulkerson [12], which represents movement of commodities over time in a network. In this model, we are given a graph with source vertices and sink vertices. Each source vertex is associated with a positive weight, called a supply, each sink vertex is associated with a positive weight, called a demand, and each edge is associated with positive length and capacity. An edge capacity limits the amount of supply that can enter the edge per unit time. One variant of the dynamic flow problem is the quickest transshipment problem, of which the objective is to send exactly the right amount of supply out of sources into sinks with satisfying the demand constraints in the minimum overall time. Hoppe and Tardos [22] provided a polynomial time algorithm for this problem in the case where the transit times are integral. However, the complexity of their algorithm is very high. Finding a practical polynomial time solution to this problem is still open. A reader is referred to a recent survey by Skutella [27] on dynamic flows.

This paper discusses a related problem, called the sink location problem [5,6,7, 10, 11, 20, 21, 26], of which the objective is to find a location of sinks in a given dynamic flow network so that all the supply is sent to the sinks as quickly as possible. For the optimality of location, the following two criteria can be naturally considered: the minimization of evacuation completion time and aggregate evacuation time (i.e., sum of evacuation times). We call the sink location problem that requires finding a location of sinks on a dynamic flow network that minimizes the evacuation completion time (resp. the aggregate evacuation time) the CTSL problem (resp. the ATSL problem). Several papers have studied the CTSL problems [7, 10, 11, 20, 21, 26]. On the other hand, for the ATSL problems, we have a few results only for path networks [5, 6, 21].

In order to model the evacuation behavior of people, it might be natural to treat each supply as a discrete quantity as in [22, 26]. Nevertheless, almost all the previous papers on sink location problems [7, 10, 11, 20, 21] treat each supply as a continuous quantity since it is easier for mathematically handling the problems and the effect of such treatment is small enough to ignore when the number of people is large. Throughout the paper, we adopt the model with continuous supplies.

Although the above two criteria are reasonable, they may not be practical since the population distribution is assumed to be fixed. In a real situation, the number of people in an area may vary depending on the time, e.g., in an office area in a big city, there are many people during the daytime on weekdays while there are much less people on weekends or during the night time. In order to take such the uncertainty into account, Kouvelis and Yu [23] introduced the minmax regret model. In the minmax regret sink location problems, we are given a finite or infinite set S of scenarios, where each scenario gives a particular assignment of weights on all the vertices. Here, for a sink location x and a scenario $s \in S$, we denote the evacuation completion time or aggregate evacuation time by F(x, s). Then, the problem can be understood as a 2-person Stackelberg game as follows. The first player picks a sink location x and the second player chooses a scenario $s \in S$ that maximizes the regret defined as $R(x,s) := F(x,s)-\min _x F(x,s)$. The objective of the first player is to choose x that minimizes the maximum regret. Throughout the paper, we call the minmax regret sink location problem, where the regret is defined with the evacuation completion time (resp. the aggregate evacuation time), the MMR-CTSL problem (resp. the MMR-ATSL problem). The MMR-CTSL problems have been studied so far [3, 9, 14, 18, 20, 24, 25]. On the other hand, for the MMR-ATSL problems, we have few results [8, 19] although the problems are also important theoretically and practically.

As for how to define a set of scenarios, all of the previous studies on the minmax regret sink location problems adopt the model with interval weights, in which each vertex is given the weight as a real interval, and a scenario is defined by choosing an element of the Cartesian product of all the weight intervals over the vertices. One drawback of the minmax regret model with interval weights is that each weight can take an independent value, thus we consider some extreme scenarios which may not happen in real situations, e.g, a scenario where all the vertices have maximum weights or minimum weights. To incorporate the dependency among weights of all the vertices into account, we adopt the model with parametric weights (first introduced by Vairaktarakis and Kouvelis [28] for the minmax regret median problem), in which each vertex is given the weight as a linear function in a common parameter t on a real interval, and a scenario is just determined by choosing t. Note that considering a real situation, each weight function should be more complex, however, such a function can be approximated by a piecewise linear function. Thus superimposing all such piecewise linear functions, it turns out that for a sufficiently small subinterval of t, every weight function can be regarded as linear, and by solving multiple subproblems with linear weight functions, we can obtain the solution.

In this paper, we study the MMR-ATSL problem on dynamic flow path networks with parametric weights. Our main theorem is below.

Theorem 1

(Main Results). Suppose that we are given a dynamic flow path network of n vertices with parametric weights.

• (i) The MMR-ATSL problem can be solved in time $O( n^4 2^{\alpha (n)} \alpha (n) \log n)$, where $\alpha (\cdot )$ is the inverse Ackermann function.

• (ii) When all the edge capacities are uniform, the MMR-ATSL problem can be solved in time $O( n^3 2^{\alpha (n)} \alpha (n) \log n)$.

Note that the MMR-ATSL problem with interval weights is studied by [8, 19], and only for the case with the uniform edge capacity, Higashikawa et al. [19] provide an $O(n^3)$ time algorithm, which is improved to one running in $O(n^2 \log ^2 n)$ time by [8]. However, for the case with general edge capacities, no algorithm has been known so far. Therefore, our result implies that the problem becomes solvable in polynomial time by introducing parametric weights.

The rest of the paper is organized as follows. In Sect. 2, we give the notations and the fundamental properties that are used throughout the paper. In Sect. 3, we give the key lemmas and the algorithms that solves the problems, which concludes the paper.

2 Preliminaries

For two real values a, b with $a<b$, let $[a, b] = \{t \in {\mathbb {R}} \mid a \le t \le b\}$, $(a, b) = \{t \in {\mathbb {R}} \mid a< t < b\}$, and $(a, b] = \{t \in {\mathbb {R}} \mid a < t \le b\}$.

In our problem, we are given a real interval $T = [t^{-}, t^{+}] \subset {\mathbb {R}}$ and a dynamic flow path network $\mathcal{P} = (P, \mathbf{w}(t), \mathbf{c}, \mathbf{l}, \tau )$, which consists of five elements: $P = (V, E)$ is a path with vertex set $V = \{v_i \mid 1 \le i \le n\}$ and edge set $E = \{e_i = (v_i, v_{i+1}) \mid 1 \le i \le n-1\}$, $\mathbf{w}(t)$ is a vector $\langle w_1(t), \ldots , w_n(t) \rangle$ of which component $w_i(t)$ is a weight function $w_i : T \rightarrow {\mathbb {R}}_{\ge 0}$ which is linear in a parameter t and nonnegative for any $t \in T$, a vector $\mathbf{c} = \langle c_1, \ldots , c_{n-1} \rangle$ consists of the capacity $c_i$ of edge $e_i$, a vector $\mathbf{l} = \langle \ell _1, \ldots , \ell _{n-1} \rangle$ consists of the length $\ell _i$ of edge $e_i$, and $\tau$ is the time which the supply takes to move a unit distance on any edge. Let us explain how edge capacities and lengths affect the evacuation time. Consider an evacuation under fixed $t \in T$. Suppose that at time 0, the amount w of supply is at vertex $v_{i+1}$ and going through edge $e_i$ towards vertex $v_i$. The first fraction of supply from $v_{i+1}$ can arrive at $v_i$ at time $\tau \ell _i$. The edge capacity $c_i$ represents the maximum amount of supply which can enter $e_i$ in a unit time interval, so all the supply w can complete leaving $v_{i+1}$ at time $w/c_i$. Therefore, all the supply w can complete arriving at $v_{i}$ at time $\tau \ell _i+w/c_i$.

For any integers i, j with $1 \le i \le j \le n$, we denote the sum of weights from $v_i$ to $v_j$ by $W_{i,j}(t) = \sum _{h=i}^{j} w_h(t)$. For the notation, we define $W_{i,j}(t) = 0$ for i, j with $i > j$. For a vertex $v_i \in V$, we abuse $v_i$ to denote the distance between $v_1$ and $v_i$, i.e., $v_i = \sum _{j=1}^{i-1} \ell _j$. For an edge $e_i \in E$, we abuse $e_i$ to denote a real open interval $(v_i,v_{i+1})$. We also abuse P to denote a real closed interval $[0,v_n]$. If a real value x satisfies $x \in (v_i, v_{i+1})$, x is said to be a point on edge $e_i$ to which the distance from $v_i$ is value $x-v_i$. Let $C_{i,j}$ be the minimum capacity for all the edges from $e_i$ to $e_j$, i.e., $C_{i,j} = \min \{c_{h} \mid i \le h \le j \}$.

Note that we precompute values $v_i$ and $W_{1,i}(t)$ for all i in O(n) time, and then, $W_{i,j}(t)$ for any i, j can be obtained in O(1) time as $W_{i,j}(t)=W_{1,j}(t)-W_{1,i-1}(t)$. In addition, $C_{i,j}$ for any i, j can be obtained in O(1) time with O(n) preprocessing time, which is known as the range minimum query [2, 4].

2.1 Evacuation Completion Time on a Dynamic Flow Path Network

In this section, we see the details of evacuation phenomenon using a simple example, and eventually show the general formula of evacuation completion time on a path, first provided by Higashikawa [17]. W.l.o.g., an evacuation to a sink x follows the first-come first-served manner at each vertex, i.e., when a small fraction of supply arrives at a vertex v on its way to x, it has to wait for the departure if there already remains some supply waiting for leaving v.

Let us consider an example with $|V|=3$ where $V=\{v_1, v_2, v_3\}, E=\{e_1=(v_1, v_2), e_2=(v_2,v_3)\}$. Assume that the sink x is located at $v_1$, and under a fixed parameter $t \in T$, the amount of supply at $v_i$ is $w_i$ for $i=2,3$.

All the supply $w_1$ at $v_1$ immediately completes its evacuation at time 0 and we send all the supply $w_2$ and $w_3$ to $v_1$ as quickly as possible. Let us focus on how the supply of $v_3$ moves to $v_1$. First, the foremost fraction of supply from $v_3$ arrives at $v_2$ at time $\tau \ell _2$, and all the supply $w_3$ completes leaving $v_3$ at time $w_3/c_2$, i.e., it completes arriving at $v_2$ at time $\tau \ell _2 + w_3/c_2$. Suppose that at time $\tau \ell _2 + w_3/c_2$, the amount $w' (\ge 0)$ of supply remains at $v_2$. From then on, the time required to send all the supply $w'$ to $v_1$ is $\tau \ell _1 + w'/c_2$. Thus, the evacuation completion time is expressed as

$$\begin{aligned} \tau (\ell _1+\ell _2) + \frac{w_3}{ c_2 } + \frac{w'}{c_1}. \end{aligned}$$

(1)

We observe what value $w'$ takes in the following cases.

Case 1: It Holds $\varvec{c}_{\varvec{1}} \varvec{\ge } \varvec{c}_{\varvec{2}}$. In this case, the amount of supply at $v_2$ should be non-increasing, because the amount $c_1$ of supply leaves $v_2$ and the amount at most $c_2$ of supply arrives at $v_2$ per unit time. Let us consider the following two situations at time $\tau \ell _2 + w_3/c_2$: When all the supply $w_3$ completes arriving at $v_2$, there remains no supply at $v_2$, that is, $w' = 0$ holds or not. If $w'=0$ holds, then substituting it into (1), the evacuation completion time is expressed as

$$\begin{aligned} \tau (\ell _1+\ell _2) + \frac{w_3}{ c_2 }. \end{aligned}$$

(2)

Otherwise, that is $w' > 0$ holds, there remains a certain amount of supply at $v_2$ even at time $\tau \ell _2$ since the amount of supply at $v_2$ is non-increasing. Thus at time $\tau \ell _2$, the amount $w_2-c_1 \tau \ell _2$ of supply remains at $v_2$. From time $\tau \ell _2$ to time $\tau \ell _2 + w_3/c_2$, the amount of supply waiting at $v_2$ decreases by $c_1-c_2$ per unit time. Then, we have

$$ w' = w_2 - c_1(\tau \ell _2) - (c_1-c_2) \cdot \frac{w_3}{c_2} = w_2 + w_3 - c_1 \tau \ell _2 - \frac{c_1 w_3}{c_2}. $$

Thus, the evacuation completion time is expressed as

$$\begin{aligned} \tau (\ell _1 + \ell _2) + \frac{w_3}{c_2} + \frac{w_2 + w_3 - c_1\tau \ell _2 - c_1 w_3 / c_2}{c_1} = \tau \ell _1 + \frac{w_2 + w_3}{ c_1 }. \end{aligned}$$

(3)

Case 2: It Holds $\varvec{c}_{\varvec{1}} \varvec{<} \varvec{c}_{\varvec{2}}$. In this case, the amount of supply waiting at $v_2$ increases by $c_2-c_1$ per unit time from time $\tau \ell _2$ (when the foremost supply from $v_3$ arrives at $v_2$) to time $\tau \ell _2 + w_3/c_2$ (when the supply from $v_3$ completes to arrive at $v_2$). Let us consider the following two situations at time $\tau \ell _2$. When the foremost supply from $v_3$ arrives at $v_2$, there remains no supply at $v_2$ or not.

If there remains no supply at $v_2$ at time $\tau \ell _2$, then it holds $w'=(c_2-c_1)(w_3/c_2) = w_3 - c_1 w_3/c_2$ in (1). Thus, the evacuation completion time is expressed as

$$\begin{aligned} \tau (\ell _1 + \ell _2) + \frac{w_3}{c_2} + \frac{w_3 - c_1 w_3/c_2}{c_1} = \tau (\ell _1+\ell _2) + \frac{w_3}{ c_1 }. \end{aligned}$$

(4)

Otherwise, the situation is similar to the latter case of Case 1. The difference is that the amount of supply waiting at $v_2$ increases by $c_2-c_1$ per unit time during from time $\tau \ell _2$ to time $\tau \ell _2 + w_3/c_2$, while in Case 1, it decreases by $c_1-c_2$ per unit time. For this case, the evacuation completion time is given by formula (3).

In summary of formulae (2)–(4), the evacuation completion time for a dynamic flow path network with three vertices is given by the following formula:

$$\begin{aligned} \max \left\{ \tau \ell _1 + \frac{w_2+w_3}{c_1}, \tau (\ell _1+\ell _2) + \frac{w_3}{\min \{c_1, c_2\}}\right\} . \end{aligned}$$

(5)

Let us turn to the case with n vertices, that is, $V = \{v_i \mid 1 \le i \le n\}$. When the sink is located at $v_1$ and a parameter $t \in T$ is fixed, generalizing formula (5), the evacuation completion time is given by the following formula, which is provided by Higashikawa [17]:

$$\begin{aligned} \max _{2 \le i \le n} \left\{ \tau \sum _{j=1}^{i-1} \ell _{j} + \frac{ \sum _{j=i}^{n}w_j(t)}{ \min _{1 \le j \le i-1} c_j} \right\} = \max _{2 \le i \le n} \left\{ \tau v_{i} + \frac{W_{i,n}(t)}{C_{1,i}} \right\} . \end{aligned}$$

(6)

An interesting observation is that each $\tau v_{i} + W_{i,n}(t)/C_{1,i}$ in (6) is equivalent to the evacuation completion time for the transformed input so that only $v_i$ is given supply $W_{i,n}(t)$ and all the others are given zero supply.

Let us give explicit formula of the evacuation completion time for fixed $x \in P$ and parameter $t \in T$. Suppose that a sink x is on edge $e_i = (v_{i}, v_{i+1})$. In this case, all the supply on the right side (i.e., at $v_{i+1}, \ldots , v_n$) will flow left to sink x and all the supply on the left side (i.e., at $v_{1}, \ldots , v_{i}$) will flow right to sink x. First, we consider the evacuation for the supply on the right side of x. Supply on the path is viewed as a continuous value, and we regard that all the supply on the right side of x is mapped to the interval $(0, W_{i+1,n}(t)]$. The value z satisfying $z \in (W_{i+1,j-1}(t), W_{i+1,j}(t)]$ with $i+1 \le j\le n$ represents all the supply at vertices $v_{i+1}, v_{i+2}, \ldots , v_{j-1}$ plus partial supply of $z - W_{i+1,j-1}(t)$ at $v_j$. Let $\theta ^{e_i}_{R} (x, t, z)$ denote the time at which the first z amount of supply on the right side of x (i.e., $v_{i+1}, v_{i+2}, \ldots , v_n$) completes its evacuation to sink x. Modifying formula (6), $\theta ^{e_i}_{R} (x, t, z)$ is given by the following formula: For $z \in (W_{i+1,j-1}(t), W_{i+1,j}(t)]$ with $i+1 \le j\le n$,

$$\begin{aligned} \theta ^{e_i}_{\mathrm{R}} (x, t, z)= & {} \max _{i+1 \le h \le j} \left\{ \tau (v_h - x) + \frac{z - W_{i+1,h-1}(t)}{C_{i, h}} \right\} . \end{aligned}$$

(7)

In a symmetric manner, we consider the evacuation for the supply on the left side of x (i.e., $v_1, \ldots , v_i$). The value z satisfying $z \in (W_{j+1,i}(t),W_{j,i}(t)]$ with $1 \le j\le i$ represents all the supply at vertices $v_i, v_{i-1}, \ldots , v_{j+1}$ plus partial supply of $z - W_{j+1,i}(t)$ at $v_j$. Let $\theta ^{e_i}_{L} (x, t, z)$ denote the time at which the first z amount of supply on the left side of x completes its evacuation to sink x, which is given by the following formula: For $z \in (W_{j+1,i}(t),W_{j,i}(t)]$ with $1 \le j\le i$,

$$\begin{aligned} \theta ^{e_i}_{\mathrm{L}} (x, t, z)= & {} \max _{j \le h \le i} \left\{ \tau (x - v_h) + \frac{z - W_{h+1,i}(t)}{C_{h,i}} \right\} . \end{aligned}$$

(8)

Let us turn to the case that sink x is at a vertex $v_i \in V$. We confirm that the evacuation times when the amount z of supply originating from the right side of and the left side of $v_i$ to sink $v_i$ are given by $\theta ^{e_{i}}_{\mathrm{R}} (v_i, t, z)$ and $\theta ^{e_{i-1}}_{\mathrm{L}}(v_i, t, z)$, respectively.

2.2 Aggregate Evacuation Time

Let $\varPhi (x, t)$ be the aggregate evacuation time (i.e., sum of evacuation time) when a sink is at a point $x \in P$ and the weight functions are fixed by a parameter $t \in T$. For a point x on edge $e_i$ and a parameter $t \in T$, the aggregate evacuation time $\varPhi (x,t)$ is defined by the integrals of the evacuation completion times $\theta ^{e_i}_{\mathrm{L}} (x, t, z)$ over $z \in [0,W_{1,i}(t)]$ and $\theta ^{e_i}_{\mathrm{R}} (x, t, z)$ over $z \in [0,W_{i+1,n}(t)]$, i.e.,

$$\begin{aligned} \varPhi (x, t) = \int _{0}^{W_{1,i}(t)} \theta ^{e_i}_{\mathrm{L}} (x, t, z) dz + \int _{0}^{W_{i+1,n}(t)} \theta ^{e_i}_{\mathrm{R}} (x, t, z) dz. \end{aligned}$$

(9)

In a similar way, if a sink x is at vertex $v_i$, then $\varPhi (v_i, t)$ is given by

$$\begin{aligned} \varPhi (v_i, t) = \int _{0}^{W_{1, i-1}(t)} \theta ^{e_{i-1}}_{\mathrm{L}} (v_i, t, z) dz + \int _{0}^{W_{i+1,n}(t)} \theta ^{e_i}_{\mathrm{R}} (v_i, t, z) dz. \end{aligned}$$

(10)

2.3 Minmax Regret Formulation

We denote by $\mathrm{Opt}(t)$ the minimum aggregate evacuation time with respect to a parameter $t \in T$. Higashikawa et al. [21] and Benkoczi et al. [6] showed that for the minsum k-sink location problems, there exists an optimal k-sink such that all the k sinks are at vertices. This implies that we have

$$\begin{aligned} \mathrm{Opt}(t) = \min _{x \in V} \varPhi (x, t) \end{aligned}$$

(11)

for any $t \in T$. For a point $x \in P$ and a value $t \in T$, a regret R(x, t) with regard to x and t is a gap between $\varPhi (x,t)$ and $\mathrm{Opt}(t)$ that is defined as

$$\begin{aligned} R(x, t) = \varPhi (x,t) - \mathrm{Opt}(t). \end{aligned}$$

(12)

The maximum regret for a sink $x \in P$, denoted by MR(x), is the maximum value of R(x, t) with respect to $t \in T$. Thus, MR(x) is defined as

$$\begin{aligned} MR(x) = \max _{t \in T} R(x,t). \end{aligned}$$

(13)

Given a dynamic flow path network $\mathcal{P}$ and a real interval T, the problem MMR-ATSL is defined as follows:

$$\begin{aligned} \text { minimize } MR(x) \text { subject to } x\in P \end{aligned}$$

(14)

Let $x^*$ denote an optimal solution of (14).

2.4 Piecewise Functions and Upper/Lower Envelopes

A function $f: X (\subset {\mathbb {R}}) \rightarrow {\mathbb {R}}$ is called a piecewise polynomial function if and only if real interval X can be partitioned into subintervals $X_1, X_2, \ldots , X_m$ so that f forms as a polynomial $f_i$ on each $X_i$. We denote such a piecewise polynomial function f by $f = \langle (f_1, X_1), \ldots , (f_m, X_m) \rangle$, or simply $f = \langle (f_i, X_i) \rangle$. We assume that such a partition into subintervals are maximal in the sense that $f_i\ne f_{i+1}$ for any i. We call each pair $(f_i, X_i)$ a piece of f, and an endpoint of the closure of $X_i$ a breakpoint of f. A piecewise polynomial function $f = \langle (f_i, X_i) \rangle$ is called a piecewise polynomial function of degree at most two if and only if each $f_i$ is quadratic or linear. We confirm the following property about the sum of piecewise polynomial functions.

Proposition 1

Let m and $m'$ be positive integers, and $f, g: X (\subset {\mathbb {R}}) \rightarrow {\mathbb {R}}$ be piecewise polynomial functions of degree at most two with m and $m'$ pieces, respectively. Then, a function $h = f + g$ is a piecewise polynomial function of degree at most two with at most $m + m'$ pieces. Moreover, given $f = \langle (f_i, X_i) \rangle$ and $g = \langle (g_j, X'_j) \rangle$, we can obtain $h = f + g = \langle (h_j, X''_j) \rangle$ in $O( m + m' )$ time.

Let $\mathcal{F} = \{f_1(y), \ldots , f_m(y)\}$ be a family of m polynomial functions where $f_i: Y_i(\subset \mathbb {R}) \rightarrow \mathbb {R}$ and Y denote the union of $Y_i$, that is, $Y = \cup _{i=1}^{m}Y_i$. An upper envelope $\mathcal{U}_{\mathcal{F}}(y)$ and a lower envelope $\mathcal{L}_{\mathcal{F}}(y)$ of $\mathcal{F}$ are functions from Y to $\mathbb {R}$ defined as follows:

$$\begin{aligned} \mathcal{U}_{\mathcal{F}}(y) = \max _{i = 1, \ldots , m} f_i(y), \,\, \mathcal{L}_{\mathcal{F}}(y) = \min _{i = 1, \ldots , m} f_i(y), \end{aligned}$$

(15)

where the maximum and the minimum are taken over those functions that are defined at y, respectively. For an upper envelope $\mathcal{U}_{\mathcal{F}}(y)$ of $\mathcal{F}$, there exist an integer sequence $U_\mathcal{F} = \langle u_1, \ldots , u_k \rangle$ and subintervals $I_1, \ldots , I_k$ of Y such that $\mathcal{U}_{\mathcal{F}}(y) = \langle (f_{u_1}(y), I_1), \ldots , (f_{u_k}(y), I_k) \rangle$ holds. That is, an upper envelope $\mathcal{U}_{\mathcal{F}}(y)$ can be represented as a piecewise polynomial function. We call the above sequence $U_\mathcal{F}$ the upper-envelope sequence of $\mathcal{U}_\mathcal{F}(y)$.

In our algorithm, we compute the upper/lower envelopes of partially defined, univariate polynomial functions. The following result is useful for this operation.

Theorem 2

([1, 15, 16]). Let $\mathcal{F}$ be a family of n partially defined, polynomial functions of degree at most two. Then, $\mathcal{U}_{\mathcal{F}}$ and $\mathcal{L}_{\mathcal{F}}$ consist of $O( n2^\alpha (n) )$ pieces and one can obtain them in time $O(n \alpha (n) \log n )$, where $\alpha (n)$ is the inverse Ackermann function. Moreover, if $\mathcal{F}$ a family of n line segments, then $\mathcal{U}_{\mathcal{F}}$ and $\mathcal{L}_{\mathcal{F}}$ consist of O(n) pieces and one can obtain them in time $O(n \log n )$.

Note that the number of pieces and the computation time for the upper/lower envelopes are involved with the maximum length of Davenport–Schinzel sequences. See [15] for the details. For a family $\mathcal{F}$ of functions, if we say that we obtain envelopes $\mathcal{U}_{\mathcal{F}}(y)$ or $\mathcal{L}_{\mathcal{F}}(y)$, then we obtain the information of all pieces $(f_{u_i}(y), I_i)$.

3 Algorithms

The main task of the algorithm is to compute the following O(n) values, MR(v) for all $v \in V$ and $\min \{ MR(x) \mid x \in e\}$ for all $e \in E$. Once we compute these values, we immediately obtain the solution of the problem by choosing the minimum one among them in O(n) time.

Let us focus on computing $\min \{ MR(x) \mid x \in e\}$ for each $e \in E$. (Note that we can compute MR(v) for $v \in V$ in a similar manner.) Recall the definition of the maximum regret for x, $MR(x) = \max \{ R(x,t) \mid t \in T \}$. A main difficulty lies in evaluating R(x, t) over $t \in T$ even for a fixed x since interval T is infinite. Furthermore, we are also required to find an optimal location among an infinite set e. To tackle with this issue, our key idea is to partition the problem into a polynomial number of subproblems as follows: We partition interval T into a polynomial number of subintervals $T_1, \ldots , T_{m}$ so that R(x, t) is represented as a (single) polynomial function in x and t on $\{x \in e\} \times T_j$ for each $j = 1, \ldots , m$. For each $T_j$, we compute the maximum regret for $x \in e$ over $T_j$ denoted by $G_j(x) =\max \{R(x,t) \mid t \in T_j\}$. An explicit form of $G_j(x)$ is given in the full paper [13]. We then obtain MR(x) for $x \in e$ as the upper envelope of functions $G_1(x), \ldots , G_{m}(x)$ and find the minimum value of MR(x) for $x \in e$ by elementary calculation.

In the rest of the paper, we mainly show that for each e or v, there exists a partition of T with a polynomial number of subintervals such that the regret R(x, t) is a polynomial function of degree at most two on each subinterval.

3.1 Key Lemmas

To understand R(x, t), we observe function $\varPhi (x,t)$. We give some other notations. Let $f^{e_i, j}_{\mathrm{R}} (t, z)$ and $f^{e_i, j}_{\mathrm{L}} (t, z)$ denote functions obtained by removing terms containing x from formulae (7) and (8). Formally, for $1 \le i < j \le n$, let function $f^{e_i, j}_{\mathrm{R}} (t, z)$ be defined on $t \in T$ and $z \in (W_{i+1,j-1}(t), W_{i+1,n}(t)]$ as

$$\begin{aligned} f^{e_i, j}_{\mathrm{R}} (t, z) = \tau v_j + \frac{z - W_{i+1,j-1}(t) }{C_{i, j}}, \end{aligned}$$

(16)

and for $1 \le j < i \le n$, let function $f^{e_i, j}_{\mathrm{L}} (t, z)$ be defined on $t \in T$ and $z \in (W_{j+1,i}(t), W_{1,i}(t)]$ as

$$\begin{aligned} f^{e_i, j}_{\mathrm{L}} (t, z) = - \tau v_j + \frac{z - W_{j+1,i}(t) }{C_{j,i}}. \end{aligned}$$

(17)

In addition, let $F^{e_i}_\mathrm{L}(t)$ and $F^{e_i}_\mathrm{R}(t)$ denote univariate functions defined as

$$\begin{aligned} F^{e_i}_\mathrm{L}(t) = \int _{0}^{W_{1,i}(t)} f^{e_i}_{\mathrm{L}} (t, z) dz, \quad F^{e_i}_\mathrm{R}(t) = \int _{0}^{W_{i+1,n}(t)} f^{e_i}_{\mathrm{R}} (t, z) dz, \end{aligned}$$

(18)

where $f^{e_i}_{\mathrm{L}} (t, z)$ and $f^{e_i}_{\mathrm{R}} (t, z)$ denote functions defined as

$$ f^{e_i}_{\mathrm{L}} (t, z) = \max _{1 \le j \le i} \left\{ f^{e_i, j}_{\mathrm{L}} (t, z) \right\} , \ f^{e_i}_{\mathrm{R}} (t, z) = \max _{i + 1 \le j \le n } \left\{ f^{e_i, j}_{\mathrm{R}} (t, z) \right\} . $$

Recall the definition of the aggregate evacuation time $\varPhi (x,t)$ shown in (9). We observe that for $x \in e_i$, $\varPhi (x,t)$ can be represented as

$$\begin{aligned} \varPhi ( x, t )= & {} \bigl (W_{1,i}(t) - W_{i+1,n}(t) \bigr ) \tau x + \!\! \int _{0}^{W_{1,i}(t)} \!\!\!\!\!\!\!\! f^{e_i}_{\mathrm{L}} (t, z) dz + \!\! \int _{0}^{W_{i+1,n}(t)} \!\!\!\!\!\!\!\! f^{e_i}_{\mathrm{R}} (t, z) dz \nonumber \\= & {} \bigl (W_{1,i}(t) - W_{i+1,n}(t) \bigr ) \tau x + F^{e_i}_\mathrm{L}(t) + F^{e_i}_\mathrm{R}(t). \end{aligned}$$

(19)

In a similar manner, by the definition of (10) and formula (18), we have

$$\begin{aligned} \varPhi ( v_i, t ) = \bigl ( W_{1,i-1}(t) - W_{i+1,n}(t) \bigr ) \tau v_i + F^{e_{i-1}}_\mathrm{L}(t) + F^{e_i}_\mathrm{R}(t). \end{aligned}$$

(20)

Let us focus on function $F^e_\mathrm{R}(t)$. As t increases, while the upper-envelope sequence of $f_\mathrm{R}^e(t,z)$ w.r.t. z remains the same, function $F^e_\mathrm{R}(t)$ is represented as the same polynomial, whose degree is at most two by formulae (16), (17) and (18). In other words, a breakpoint of $F^e_\mathrm{R}(t)$ corresponds to the value t such that the upper-envelope sequence of $f_\mathrm{R}^e(t,z)$ w.r.t. z changes. We notice that such a change happens only when three functions $f^{e, h}_{\mathrm{R}} (t, z)$, $f^{e, i}_{\mathrm{R}} (t, z)$ and $f^{e, j}_{\mathrm{R}} (t, z)$ intersect each other, which can happen at most once. This implies that $F^e_\mathrm{R}(t)$ consists of $O(n^3)$ breakpoints, that is, it is a piecewise polynomial function of degree at most two with $O(n^3)$ pieces. The following lemma shows that the number of pieces is actually $O(n^2)$. See [13] for details of the proof.

Lemma 1

For each $e \in E$, $F^{e}_\mathrm{L}(t)$ and $F^{e}_\mathrm{R}(t)$ are piecewise polynomial functions of degree at most two with $O(n^2)$ pieces, and can be computed in $O(n^3 \log n)$ time. Especially, when all the edge capacities are uniform, the numbers of pieces of them are O(n), and can be computed in $O(n^2 \log n)$ time.

Let $N_{F}$ denote the maximum number of pieces of $F^{e}_\mathrm{L}(t)$ and $F^{e}_\mathrm{R}(t)$ over $e \in E$. Then we have $N_{F} = O(n^2)$, and for the case with uniform edge capacity, $N_{F} = O(n)$. Next, we consider $\mathrm{Opt}(t) = \min \{ \varPhi (x,t) \mid x \in V\}$, which is the lower envelope of a family of n functions $\varPhi (v_i, t)$ in t. Theorem 2 and Lemma 1 imply the following lemma. See [13] for the proof.

Lemma 2

$\mathrm{Opt}(t)$ is a piecewise polynomial function of degree at most two with $O(n N_{F}2^{\alpha (n)})$ pieces, and can be obtained in $O(n N_{F} \alpha (n) \log n)$ time if functions $F^{e}_\mathrm{L}(t)$ and $F^{e}_\mathrm{R}(t)$ for all $e \in E$ are available.

Let $N_\mathrm{Opt}$ denote the number of pieces of $\mathrm{Opt}(t)$. Then we have $N_\mathrm{Opt} = O(n N_{F}2^{\alpha (n)})$.

Let us consider R(x, t) in the case that sink x is on an edge $e_i \in E$. Substituting formula (19) for (12), we have

$$ R(x, t) = \varPhi (x,t) - \mathrm{Opt}(t) = \bigl ( W_{1,i}(t) - W_{i+1,n}(t) \bigr ) \tau x + F^{e_i}_\mathrm{L}(t)+ F^{e_i}_\mathrm{R}(t) - \mathrm{Opt}(t). $$

By Proposition 1, $F^{e_i}_\mathrm{L}(t)+ F^{e_i}_\mathrm{R}(t) - \mathrm{Opt}(t)$ is a piecewise polynomial function of degree at most two with at most $2 N_{F} + N_\mathrm{Opt} = O(N_\mathrm{Opt})$ pieces. Let $N_{e_i}$ be the number of pieces of $F^{e_i}_\mathrm{L}(t)+ F^{e_i}_\mathrm{R}(t) - \mathrm{Opt}(t)$ and $T^{e_i}_j$ be the interval of the j-th piece (from the left) of $F^{e_i}_\mathrm{L}(t)+ F^{e_i}_\mathrm{R}(t) - \mathrm{Opt}(t)$. Thus, R(x, t) is represented as a (single) polynomial function in x and t on $\{x \in e\} \times T_j$ for each $T_j$. For each integer j with $1 \le j \le N_{e_i}$, let $G^{e_i}_{j}(x)$ be a function defined as

$$\begin{aligned} G^{e_i}_{j}(x) = \max \{ R(x, t) \mid t \in T^{e_i}_j\}. \end{aligned}$$

(21)

We then have the following lemma. See [13] for the proof.

Lemma 3

For each $e_i \in E$ and j with $1 \le j \le N_{e_i}$, $G^{e_i}_{j}(x)$ is a piecewise polynomial function of degree at most two with at most three pieces, and can be obtained in constant time if functions $F^{e_i}_\mathrm{L}(t)$, $F^{e_i}_\mathrm{R}(t)$ and $\mathrm{Opt}(t)$ are available.

Recalling the definition of MR(x), it holds that for $x \in e$,

$$ MR(x) = \max \{R(x, t) \mid t \in T \} = \max \{G^{e}_{j}(x) \mid 1 \le j \le N_{e} \}, $$

that is, MR(x) is the upper envelope of functions $G^{e}_{1}(x), \ldots , G^{e}_{N_{e}}(x)$. Applying Theorem 2, we have the following lemma. See [13] for the proof.

Lemma 4

For each $e \in E$, there exists an algorithm that finds a location that minimizes MR(x) under the restriction with $x \in e$ in $O(N_\mathrm{Opt} \alpha (n) \log n)$ time if functions $F^{e}_\mathrm{L}(t)$, $F^{e}_\mathrm{R}(t)$ and $\mathrm{Opt}(t)$ are available.

3.2 Algorithms and Time Analyses

Let us give an algorithm that finds a sink location that minimizes the maximal regret and the analysis of the running time of each step.

First, we obtain $F^e_\mathrm{L}(t)$ and $F^e_\mathrm{R}(t)$ for all $e \in E$, and function $\mathrm{Opt}(t)$ as a preprocess. Applying Lemmas 1 and 2, we take $O(n^2 N_{F} \log n)$ time for these operations. Next, we compute $x^{*,e} = \mathop {\mathrm {arg}\,\mathrm {min}}\limits \{ MR(x) \mid x \in e\}$ for all $e \in E$ in $O(n N_\mathrm{Opt} \alpha (n) \log n)$ time by applying Lemma 4. Note that the small modification for the algorithm of Lemma 4 leads that we can also compute MR(v) for all $v \in V$ in $O(n N_\mathrm{Opt})$ time. (See Lemma 5 in [13].) Finally, we find an optimal sink location $x^{*}$ in O(n) time by evaluating the values MR(x) for $x \in \{ x^{*, e} \} \cup V$.

Since we have $N_{Opt} = O(n N_{F} 2^{\alpha (n)})$, the bottleneck of our algorithm is to compute $x^{*,e}$ for all $e \in E$. Thus, we see that the algorithm runs in $O(n^2 N_{F}2^{\alpha (n)} \alpha (n) \log n)$ time, which completes the proof of our main theorem because $N_{F} = O(n^2)$, and for the case with uniform edge capacity, $N_{F} = O(n)$.