Almost Linear Time Algorithms for Minsum k-Sink Problems on Dynamic Flow Path Networks

Abstract

We address the facility location problems on dynamic flow path networks. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and positive 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. In the dynamic flow network, given particular points on edges or vertices, called sinks, all the people evacuate from the vertices to the sinks as quickly as possible. The problem is to find the location of sinks on a dynamic flow path network in such a way that the aggregate evacuation time (i.e., the sum of evacuation times for all the people) to sinks is minimized. We consider two models of the problem: the confluent flow model and the non-confluent flow model. In the former model, the way of evacuation is restricted so that all the people at a vertex have to evacuate to the same sink, and in the latter model, there is no such restriction. In this paper, for both the models, we develop algorithms which run in almost linear time regardless of the number of sinks. It should be stressed that for the confluent flow model, our algorithm improves upon the previous result by Benkoczi et al. [Theoretical Computer Science, 2020], and one for the non-confluent flow model is the first polynomial time algorithm.

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

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  [10], 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  [15] 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  [18] on dynamic flows.

This paper discusses a related problem, called the k-sink problem  [2, 4, 5, 7,8,9, 12, 13, 16], of which the objective is to find a location of k 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., average evacuation time). We call the k-sink problem that requires finding a location of k sinks that minimizes the evacuation completion time (resp. the aggregate evacuation time) the minmax (resp. minsum) k-sink problem. Several papers have studied the minmax k-sink problems on dynamic flow networks  [2, 7,8,9, 12, 13, 16]. On the other hand, the minsum k-sink problems on dynamic flow networks have not been studied except for the case of path networks  [4, 5, 13].

Moreover, there are two models on the way of evacuation. Under the confluent flow model, all the supply leaving a vertex must evacuate to the same sink through the same edges, and under the non-confluent flow model, there is no such restriction. To our knowledge, all the papers which deal with the k-sink problems  [2, 4, 5, 7,8,9, 13] adopt the confluent flow model.

In order to model the evacuation behavior of people, it might be natural to treat each supply as a discrete quantity as in  [15, 16]. Nevertheless, almost all the previous papers on sink problems  [2, 7,8,9, 12, 13] treat each supply as a continuous quantity since it is easier for mathematically handling the problems and the effect is small enough to ignore when the number of people is large. Throughout the paper, we also adopt the model with continuous supplies.

In this paper, we study the minsum k-sink problems on dynamic flow path networks under both the confluent flow model and the non-confluent flow model. A path network can model a coastal area surrounded by the sea and a hilly area, an airplane aisle, a hall way in a building, a street, a highway, etc., to name a few. For the confluent flow model, the previous best results are an $O(kn \log ^3 n)$ time algorithm for the case with uniform edge capacity in [4], and $O(kn \log ^4 n)$ time algorithm for the case with general edge capacities in [5], where n is the number of vertices on path networks. We develop algorithms which run in time $\min \{ O(kn \log ^2 n),n 2^{O(\sqrt{\log k \log \log n})} \log ^2 n \}$ for the case with uniform edge capacity, and in time $\min \{ O(kn \log ^3 n),n 2^{O(\sqrt{\log k \log \log n})} \log ^3 n \}$ for the case with general edge capacities, respectively. Thus, our algorithms improve upon the complexities by [4, 5] for any value of k. Especially, for the non-confluent flow model, this paper provides the first polynomial time algorithms.

Since the number of sinks k is at most n, we confirm $2^{O(\sqrt{\log k \log \log n})} = n^{O( \sqrt{\log \log n/\log n})}= n^{o(1)}$, which means that our algorithms are the first ones which run in almost linear time (i.e., $n^{1+o(1)}$ time) regardless of k. The reason why we could achieve almost linear time algorithms for the minsum k-sink problems is that we newly discover a convex property from a novel point of view. In all the previous papers on the k-sink problems, the evacuation completion. time and the aggregate evacuation time (called $\mathsf {CT}$ and $\mathsf {AT}$, respectively) are basically determined as functions in “distance”: Let us consider the case with a 1-sink. The values $\mathsf {CT}(x)$ or $\mathsf {AT}(x)$ may change as a sink location x moves along edges in the network. In contrast, we introduce a new metric for $\mathsf {CT}$ and $\mathsf {AT}$ as follows: assuming that a sink is fixed and all the supply in the network flows to the sink, for a positive real z, $\mathsf {CT}(z)$ is the time at which the first z of supply completes its evacuation to the sink and then $\mathsf {AT}(z)$ is the integral of $\mathsf {CT}(z)$, i.e., $\mathsf {AT}(z)=\int _0^z \mathsf {CT}(t)dt$. We can observe that $\mathsf {AT}(z)$ is convex in z since $\mathsf {CT}(z)$ is increasing in z. Based on the convexity of $\mathsf {AT}(z)$, we develop efficient algorithms.

The rest of the paper is organized as follows. In Sect. 2, we introduce the terms that are used throughout the paper and explain our models. In Sect. 3, we show that our problem can be reduced to the minimum k-link path problem with links satisfying the concave Monge condition. This immediately implies by Schieber  [17] that the optimal solutions for our problems can be obtained by solving $\min \{ O(kn),n 2^{O(\sqrt{\log k \log \log n})}\}$ subproblems of computing the optimal aggregate evacuation time for subpaths, in each of which two sinks are located on its endpoints. Section 3 subsequently shows an overview of the algorithm that solves the above subproblems. In Sect. 4, we introduce novel data structures, which enable to solve each of the above subproblems in $O(\mathrm{poly}\log n)$ time. Section 5 concludes the paper.

2 Preliminaries

2.1 Notations

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 \le t < b\}$, $(a,b]=\{t \in \mathbb {R} \mid a < t \le b\}$, and $(a,b)=\{t \in \mathbb {R} \mid a< t < b\}$, where $\mathbb {R}$ is the set of real values. For two integers i, j with $i \le j$, let $[i..j]=\{h \in \mathbb {Z} \mid i \le h \le j\}$, where $\mathbb {Z}$ is the set of integers. A dynamic flow path network $\mathcal {P}$ is given as a 5-tuple $(P,{\mathbf{w}},{\mathbf{c}},{\mathbf{l}},\tau )$, where P is a path with vertex set $V = \{v_i \mid i \in [1..n]\}$ and edge set $E = \{e_i = (v_i, v_{i+1}) \mid i \in [1..n-1]\}$, ${\mathbf{w}}$ is a vector $\langle w_1, \ldots , w_n \rangle$ of which a component $w_i$ is the weight of vertex $v_i$ representing the amount of supply (e.g., the number of evacuees, cars) located at $v_i$, ${\mathbf{c}}$ is a vector $\langle c_1, \ldots , c_{n-1} \rangle$ of which a component $c_i$ is the capacity of edge $e_i$ representing the upper bound on the flow rate through $e_i$ per unit time, ${\mathbf{l}}$ is a vector $\langle \ell _1, \ldots , \ell _{n-1} \rangle$ of which a component $\ell _i$ is the length of edge $e_i$, and $\tau$ is the time which unit supply takes to move unit distance on any edge.

We say a point p lies on path $P = (V, E)$, denoted by $p \in P$, if p lies on a vertex $v \in V$ or an edge $e \in E$. For two points $p, q \in P$, $p \prec q$ means that p lies to the left side of q. For two points $p, q \in P$, $p \preceq q$ means that $p \prec q$ or p and q lie on the same place. Let us consider two integers $i,j \in [1..n]$ with $i<j$. We denote by $P_{i,j}$ a subpath of P from $v_i$ to $v_j$. Let $L_{i,j}$ be the distance between $v_i$ and $v_j$, i.e., $L_{i,j} = \sum _{h=i}^{j-1}\ell _h$, and let $C_{i,j}$ be the minimum capacity for all the edges between $v_i$ and $v_j$, i.e., $C_{i,j} = \min \{ c_{h} \mid h \in [i..j-1]\}$. For $i \in [1..n]$, we denote the sum of weights from $v_1$ to $v_i$ by $W_i = \sum _{j=1}^{i}w_j$. Note that, given a dynamic flow path network $\mathcal {P}$, if we construct two lists of $W_i$ and $L_{1,i}$ for all $i \in [1..n]$ in O(n) preprocessing time, we can obtain $W_i$ for any $i \in [1..n]$ and $L_{i,j} = L_{1,j}-L_{1,i}$ for any $i,j \in [1..n]$ with $i<j$ in O(1) time. In addition, $C_{i,j}$ for any $i,j \in [1..n]$ with $i<j$ can be obtained in O(1) time with O(n) preprocessing time, which is known as the range minimum query  [1, 3].

A k-sink $\mathbf{x}$ is k-tuple $(x_1, \ldots , x_k)$ of points on P, where $x_i \prec x_j$ for $i<j$. We define the function $\mathrm {Id}$ for point $p \in P$ as follows: the value $\mathrm {Id}(p)$ is an integer such that $v_{\mathrm {Id}(p)} \preceq p \prec v_{\mathrm {Id}(p)+1}$ holds. For a k-sink $\mathbf{x}$ for $\mathcal {P}$, a divider $\mathbf{d}$ is $(k-1)$-tuple $(d_1, \ldots , d_{k-1})$ of real values such that $d_i < d_j$ for $i<j$ and $W_{\mathrm {Id}(x_i)} \le d_i \le W_{\mathrm {Id}(x_{i+1})}$. Given a k-sink $\mathbf{x}$ and a divider $\mathbf{d}$ for $\mathcal {P}$, the portion $W_{\mathrm {Id}(x_i)} - d_{i-1}$ supply that originates from the left side of $x_i$ flows to sink $x_i$, and the portion $d_{i} - W_{\mathrm {Id}(x_i)}$ supply that originates from the right side of $x_i$ also flows to sink $x_i$. For instance, under the non-confluent flow model, if $W_{h-1}< d_i < W_{h}$ where $h \in [1..n]$, $d_i - W_{h-1}$ of $w_h$ supply at $v_h$ flows to sink $x_{i}$ and the rest of $W_{h} - d_i$ supply to do sink $x_{i+1}$. The difference between the confluent flow model and the non-confluent flow model is that the confluent flow model requires that each value $d_i$ of a divider $\mathbf{d}$ must take a value in $\{W_1, \ldots , W_n\}$, but the non-confluent flow model does not. For the notation, we set $d_0 = 0$ and $d_k = W_n$.

For a dynamic flow path network $\mathcal {P}$, a k-sink x and a divider d, the evacuation completion time $\mathsf {CT}(\mathcal {P}, \mathbf{x}, \mathbf{d})$ is the time at which all the supply completes the evacuation. The aggregate evacuation time $\mathsf {AT}(\mathcal {P}, \mathbf{x}, \mathbf{d})$ is that the sum of the evacuation completion time for all the supply. Their explicit definitions are given later. In this paper, our task is, given a dynamic flow path network $\mathcal {P}$, to find a k-sink x and a divider d that minimize the aggregate evacuation time $\mathsf {AT}(\mathcal {P}, \mathbf{x}, \mathbf{d})$ in each evacuation model.

2.2 Aggregate Evacuation Time on a Path

For the confluent flow model, it is shown in  [5, 13] that for the minsum k-sink problems, there exists an optimal k-sink such that all the k sinks are at vertices. This fact also holds for the non-confluent flow model. Indeed, if a divider d is fixed, then we have k subproblems for a 1-sink and the optimal sink location for each subproblem is at a vertex. Thus, we have the following lemma.

Lemma 1

( [13]). For the minsum k-sink problem in a dynamic flow path network, there exists an optimal k-sink such that all the k sinks are at vertices under the confluent/non-confluent flow model.

Lemma 1 implies that it is enough to consider only the case that every sink is at a vertex. Thus, we suppose $\mathbf{x}=(x_1, \ldots , x_k) \in V^{k}$, where $x_i \prec x_j$ for $i<j$.

A Simple Example with a 1-sink. In order to give explicit definitions for the evacuation completion time and the aggregate evacuation time, let us consider a simple example for a 1-sink. We are given a dynamic flow path network $\mathcal {P}=(P,{\mathbf{w}},{\mathbf{c}},{\mathbf{l}},\tau )$ with n vertices and set a unique sink on a vertex $v_i$, that is, $\mathbf{x} = (v_i)$ and $\mathbf{d} = ()$ which is the 0-tuple. In this case, all the supply on the left side of $v_i$ (i.e., at $v_1, \ldots , v_{i-1}$) will flow right to sink $v_i$, and all the supply on the right side of $v_i$ (i.e., at $v_{i+1}, \ldots , v_n$) will flow left to sink $v_i$. Note that in our models all the supply at $v_i$ immediately completes its evacuation at time 0.

To deal with this case, we introduce some new notations. Let the function $\theta ^{i,+}(z)$ denote the time at which the first $z - W_{i}$ of supply on the right side of $v_i$ completes its evacuation to sink $v_i$ (where $\theta ^{i,+}(z) = 0$ for $z \in [0,W_i]$). Higashikawa  [11] shows that the value $\theta ^{i,+}(W_n)$, the evacuation completion time for all the supply on the right side of $v_i$, is given by the following formula:

$$\begin{aligned} \theta ^{i,+}(W_n)= & {} \max \left\{ \frac{W_{n} - W_{j-1} }{ C_{i,j} }+ \tau \cdot L_{i,j} \mid j \in [i+1..n] \right\} . \end{aligned}$$

(1)

Recall that $C_{i,j} = \min \{ c_h \mid h \in [i..j-1] \}$. We can generalize formula (1) to the case with any $z \in [0,W_n]$ as follows:

$$\begin{aligned} \theta ^{i, +}(z) = \max \{ \theta ^{i, +, j}(z) \mid j \in [i+1..n]\}, \end{aligned}$$

(2)

where $\theta ^{i, +, j}(z)$ for $j \in [i+1..n]$ is defined as

$$\begin{aligned} \theta ^{i, +, j}(z) = \left\{ \begin{array}{ll} 0 &{} \text {if } z \le W_{j-1}, \\ \frac{z - W_{j-1}}{C_{i,j}} + \tau \cdot L_{i,j} &{} \text {if } z > W_{j-1}. \end{array} \right. \end{aligned}$$

(3)

Similarly, let $\theta ^{i, -}(z)$ denote the time at which the first $W_{i-1} - z$ of supply on the left side of $v_i$ completes its evacuation to sink $v_i$ (where $\theta ^{i,-}(z) = 0$ for $z \in [W_{i-1},W_n]$). Then,

$$\begin{aligned} \theta ^{i, -}(z) = \max \{ \theta ^{i, -, j}(z) \mid j \in [1..i-1]\}, \end{aligned}$$

(4)

where $\theta ^{i, -, j}(z)$ is defined as

$$\begin{aligned} \theta ^{i, -, j}(z) = \left\{ \begin{array}{ll} \frac{W_{j} - z}{C_{j,i}} + \tau \cdot L_{j,i} &{} \text {if } z < W_j, \\ 0 &{} \text {if } z \ge W_j. \end{array} \right. \end{aligned}$$

(5)

The aggregate evacuation times for the supply on the right side and the left side of $v_i$ are

$$\begin{aligned} \int _{W_i}^{W_n}\theta ^{i, +}(z)dz = \int _{0}^{W_n}\theta ^{i, +}(z)dz \text { and } \int _{0}^{W_{i-1}}\theta ^{i, -}(z)dz = \int _{0}^{W_n}\theta ^{i, -}(z)dz, \end{aligned}$$

respectively. Thus, the aggregate evacuation time $\mathsf {AT}(\mathcal {P}, (v_i), ())$ is given as

$$\begin{aligned} \mathsf {AT}(\mathcal {P}, (v_i), ()) = \int _{0}^{W_n}\left\{ \theta ^{i, +}(z) + \theta ^{i, -}(z) \right\} dz. \end{aligned}$$

Fig. 1.

The thick half-open segments indicate function $\theta ^{i,+}(t)$ and the gray area indicates $\varPhi ^{i,+}(z)$ for some $z > W_i$.

Aggregate Evacuation Time with a k-Sink. Suppose that we are given a k-sink $\mathbf{x} = (x_1, \ldots , x_k) \in V^{k}$ and a divider $\mathbf{d} = (d_1, \ldots , d_{k-1})$. Recalling the definition of $\mathrm {Id}(p)$ for $p \in P$, we have $x_i = v_{\mathrm {Id}(x_i)}$ for all $i \in [1..k]$. In this situation, for each $i \in [1..k]$, the first $d_{i} - W_{\mathrm {Id}(x_i)}$ of supply on the right side of $x_i$ and the first $W_{\mathrm {Id}(x_i)-1} - d_{i-1}$ of supply on the left side of $x_i$ move to sink $x_i$.

By the argument of the previous section, the aggregate evacuation times for the supply on the right side and the left side of $x_i$ are

$$\begin{aligned} \int _{W_{\mathrm {Id}(x_i)}}^{d_i} \theta ^{\mathrm {Id}(x_i), +}(z)dz= & {} \int _{0}^{d_i} \theta ^{\mathrm {Id}(x_i), +}(z)dz \quad \text {and} \\ \int _{d_{i-1}}^{W_{\mathrm {Id}(x_i)-1}} \theta ^{\mathrm {Id}(x_{i}),-}(z)dz= & {} \int _{d_{i-1}}^{W_n} \theta ^{\mathrm {Id}(x_{i}),-}(z)dz, \end{aligned}$$

respectively. In order to give the general form for the above values, let us denote by $\varPhi ^{i, +}(z)$ the aggregate evacuation time when the first $z - W_{i}$ of supply on the right side of $v_i$ flows to sink $v_i$. Similarly, we denote by $\varPhi ^{i, -}(z)$ the aggregate evacuation time when the first $W_{i-1} - z$ of supply on the left side of $v_i$ flows to sink $v_i$. Therefore, we have

$$\begin{aligned} \varPhi ^{i, +}(z) = \int _{0}^{z} \theta ^{i, +}(t)dt \quad \text {and} \quad \varPhi ^{i, -}(z) = \int _{z}^{W_n} \theta ^{i,-}(t)dt = \int _{W_n}^{z} -\theta ^{i,-}(t)dt \end{aligned}$$

(6)

(see Fig. 1). Let us consider a subpath $P_{\mathrm {Id}(x_i), \mathrm {Id}(x_{i+1})}$ which is a subpath between sinks $x_{i}$ and $x_{i+1}$. The aggregate evacuation time for the supply on $P_{\mathrm {Id}(x_i), \mathrm {Id}(x_{i+1})}$ is given by

$$\begin{aligned} \int _{0}^{d_i} \theta ^{\mathrm {Id}(x_i), +}(z)dz + \int _{d_{i}}^{W_n} \theta ^{\mathrm {Id}(x_{i+1}),-}(z)dz = \varPhi ^{\mathrm {Id}(x_i), +}(d_i) + \varPhi ^{\mathrm {Id}(x_{i+1}), -}(d_i). \end{aligned}$$

For $i, j \in [1..n]$ with $i < j$, let us define

$$\begin{aligned} \varPhi ^{i, j}(z) = \varPhi ^{i, +}(z) + \varPhi ^{j,-}(z) = \int _{0}^{z} \theta ^{i, +}(t)dt + \int _{z}^{W_n} \theta ^{j, -}(t)dt \end{aligned}$$

(7)

for $z \in [W_{i}, W_{j-1}]$. Then, the aggregate evacuation time $\mathsf {AT}(\mathcal {P}, \mathbf{x}, \mathbf{d})$ is given as

$$\begin{aligned} \mathsf {AT}(\mathcal {P}, \mathbf{x}, \mathbf{d}) = \varPhi ^{\mathrm {Id}(x_1),-}(0) + \sum _{i=1}^{k-1}\varPhi ^{\mathrm {Id}(x_i), \mathrm {Id}(x_{i+1})}(d_i) + \varPhi ^{\mathrm {Id}(x_k),+}(W_n). \end{aligned}$$

(8)

In the rest of this section, we show the important properties of $\varPhi ^{i, j}(z)$. Let us first confirm that by Eq. (6), both $\varPhi ^{i, +}(z)$ and $\varPhi ^{j, -}(z)$ are convex in z since $\theta ^{i, +}(z)$ and $-\theta ^{j, -}(z)$ are non-decreasing in z, therefore $\varPhi ^{i, j}(z)$ is convex in z. On the condition of the minimizer for $\varPhi ^{i, j}(z)$, we have a more useful lemma.

Lemma 2

For any $i,j \in [1..n]$ with $i < j$, there uniquely exists

$$\begin{aligned} z^* \in \mathop {\mathrm{arg\,min}}\limits _{z \in [W_i,W_{j-1}]}\max \{\theta ^{i,+}(z), \theta ^{j,-}(z)\}. \end{aligned}$$

Furthermore, $\varPhi ^{i, j}(z)$ is minimized on $[W_i,W_{j-1}]$ when $z=z^*$.

See Lemma 2 in  [14] for the proof. In the following sections, such $z^*$ is called the pseudo-intersection point¹ of $\theta ^{i,+}(z)$ and $\theta ^{j,-}(z)$, and we say that $\theta ^{i,+}(z)$ and $\theta ^{j,-}(z)$ pseudo-intersect on $[W_i,W_{j-1}]$ at $z^*$.

3 Algorithms

In order to solve our problems, we reduce them to minimum k-link path problems. In the minimum k-link path problems, we are given a weighted complete directed acyclic graph (DAG) $G = (V', E', w')$ with $V' = \{v'_{i} \mid i \in [1..n]\}$ and $E' = \{(v'_i, v'_j) \mid i,j \in [1..n], i < j\}$. Each edge $(v'_i, v'_j)$ is associated with weight $w'(i, j)$. We call a path in G a k-link path if the path contains exactly k edges. The task is to find a k-link path $(v'_{a_0} = v'_1, v'_{a_1}, v'_{a_2}, \ldots , v'_{a_{k-1}}, v'_{a_k} = v'_n)$ from $v'_1$ to $v'_n$ that minimizes the sum of weights of k edges, $\sum _{i=1}^{k}w'(a_{i-1}, a_i)$. If the weight function $w'$ satisfies the concave Monge property, then we can solve the minimum k-link path problems in almost linear time regardless of k.

Definition 1

(Concave Monge property). We say function $f: {\mathbb Z} \times {\mathbb Z} \rightarrow {\mathbb R}$ satisfies the concave Monge property if for any integers i, j with $i+1<j$, $f(i, j) + f(i+1, j+1) \le f(i+1, j) + f(i, j+1)$ holds.

Lemma 3

( [17]). Given a weighted complete DAG with n vertices, if the weight function satisfies the concave Monge property, then there exists an algorithm that solves the minimum k-link path problem in time $\min \{O(kn),n 2^{O(\sqrt{\log k \log \log n})}\}$.

We describe how to reduce the k-sink problem on a dynamic flow path network $\mathcal {P}=(P=(V, E),{\mathbf{w}},{\mathbf{c}},{\mathbf{l}},\tau )$ with n vertices to the minimum $(k+1)$-link path problem on a weighted complete DAG $G = (V', E', w')$. We prepare a weighted complete DAG $G = (V', E', w')$ with $n+2$ vertices, where $V' = \{v'_i \mid i \in [0..n+1]\}$ and $E' = \{ (v'_i, v'_j) \mid i,j \in [0..n+1], i<j\}$. We set the weight function $w'$ as

$$\begin{aligned} w'(i,j) = \left\{ \begin{array}{lll} \mathsf {OPT}(i, j)&{} \quad &{} i, j \in [1..n], i < j, \\ \varPhi ^{i, +}(W_n) &{} &{}i \in [1..n] \text { and } j = n+1, \\ \varPhi ^{j, -}(0) &{} &{}i = 0 \text { and } j \in [1..n], \\ \infty &{} &{} i = 0 \text { and } j=n+1, \end{array} \right. \end{aligned}$$

(9)

where $\mathsf {OPT}(i, j) = \min _{z \in [W_{i}, W_{j-1}]} \varPhi ^{i, j}(z)$.

Now, on a weighted complete DAG G made as above, let us consider a $(k+1)$-link path $(v'_{a_0}=v'_0, v'_{a_1}, \ldots , v'_{a_{k}}, v'_{a_{k+1}}=v'_{n+1})$ from $v'_0$ to $v'_{n+1}$, where $a_1, \ldots , a_k$ are integers satisfying $0< a_1< a_2< \cdots< a_k < n+1$. The sum of weights of this $(k+1)$-link path is

$$\begin{aligned} \sum _{i=0}^{k}w'(a_{i}, a_{i+1})= & {} \varPhi ^{a_1, -}(0) + \sum _{i=1}^{k-1} \mathsf {OPT}(a_{i}, a_{i+1}) + \varPhi ^{a_{k}, +}(W_n). \end{aligned}$$

This value is equivalent to $\min _{\mathbf{d}} \mathsf {AT}({{\mathcal {P}}}, \mathbf{x}, \mathbf{d})$ for a k-sink $\mathbf{x} = (v_{a_1}, v_{a_2}, \ldots , v_{a_{k}})$ (recall Eq. (8)), which implies that a minimum $(k+1)$-link path on G corresponds to an optimal k-sink location for a dynamic flow path network $\mathcal {P}$.

We show in the following lemma that the function $w'$ defined as formula (9) satisfies the concave Monge property under both of evacuation models. See Lemma 4 in  [14] for the proof.

Lemma 4

The weight function $w'$ defined as formula (9) satisfies the concave Monge property under the confluent/non-confluent flow model.

Lemmas 3 and 4 imply that if we can evaluate $w'(i,j)$ in time at most t for any $i,j \in [0..n+1]$ with $i < j$, then we can solve the k-sink problem in time $\min \{O(knt), n2^{O(\sqrt{\log k \log \log n})} t \}$.

In order to obtain $w'(i,j)$ for any $i,j \in [0..n+1]$ with $i < j$ in $O(\mathrm{poly}\log n)$ time, we introduce novel data structures and some modules using them. Basically, we construct a segment tree  [6] ${\mathcal {T}}$ with root $\rho$ such that its leaves correspond to indices of vertices of P arranged from left to right and its height is $O(\log n)$. For a node $u \in {\mathcal {T}}$, let ${\mathcal {T}}_u$ denote the subtree rooted at u, and let $l_u$ (resp. $r_u$) denote the index of the vertex that corresponds to the leftmost (resp. rightmost) leaf of ${\mathcal {T}}_u$. Let $p_u$ denote the parent of u if $u \ne \rho$. We say a node $u \in {\mathcal {T}}$ spans subpath $P_{\ell _u, r_u}$. If $P_{\ell _u,r_u} \subseteq P'$ and $P_{\ell _{p_u},r_{p_u}} \not \subseteq P'$, node u is called a maximal subpath node for $P'$. For each node $u \in {\mathcal {T}}$, let $m_u$ be the number of edges in subpath $P_{\ell _u, r_u}$, i.e., $m_u = r_u - \ell _u$. As with a standard segment tree, ${\mathcal {T}}$ has the following properties.

Property 1

For $i, j \in [1..n]$ with $i<j$, the number of maximal subpath nodes for $P_{i,j}$ is $O(\log n)$. Moreover, we can find all the maximal subpath nodes for $P_{i,j}$ by walking on ${\mathcal {T}}$ from leaf i to leaf j in $O(\log n)$ time.

Property 2

If one can construct data structures for each node u of a segment tree ${\mathcal {T}}$ in $O(f(m_u))$ time, where $f:{\mathbb N} \rightarrow \mathbb {R}$ is some function independent of n and bounded below by a linear function asymptotically, i.e., $f(m)=\varOmega (m)$, then the running time for construction of data structures for every node in ${\mathcal {T}}$ is $O(f(n)\log n)$ time in total.

At each node $u \in {\mathcal {T}}$, we store four types of the information that depend on the indices of the vertices spanned by u, i.e., $l_u, \ldots , r_u$. We will introduce each type in Sect. 4. As will be shown there, the four types of the information at $u \in {\mathcal {T}}$ can be constructed in $O(m_u \log m_u)$ time. Therefore, we can construct ${\mathcal {T}}$ in $O(n\log ^2 n)$ time by Property 2.

Recall that for $i,j \in [1..n]$ with $i < j$, it holds $w'(i,j) = \mathsf {OPT}(i,j)$. We give an outline of the algorithm that computes $\mathsf {OPT}(i,j)$ only for the non-confluent flow model since a similar argument holds even for the confluent flow model with minor modification. The main task is to find a value $z^*$ that minimizes $\varPhi ^{i,j}(z)$, i.e., $\mathsf {OPT}(i,j)=\varPhi ^{i,j}(z^*)$. By Lemma 2, such the value $z^*$ is the pseudo-intersection point of $\theta ^{i,+}(z)$ and $\theta ^{j,-}(z)$ on $[W_i,W_{j-1}]$.

Before explaining our algorithms, we need introduce the following definition:

Definition 2

For integers $i,\ell ,r \in [1..n]$ with $i < \ell \le r$, we denote by $\theta ^{i, +, [\ell ..r]}(z)$ the upper envelope of functions $\{\theta ^{i, +, h}(z) \mid h \in [\ell ..r]\}$, that is,

$$\begin{aligned} \theta ^{i, +, [\ell ..r]}(z) = \max \{ \theta ^{i, +, h}(z) \mid h \in [\ell ..r]\}. \end{aligned}$$

For integers $i,\ell ,r \in [1..n]$ with $\ell \le r < i$, we denote by $\theta ^{i, -, [\ell ..r]}(z)$ the upper envelope of functions $\{\theta ^{i, -, h}(z) \mid h \in [\ell ..r]\}$, that is,

$$\begin{aligned} \theta ^{i, -, [\ell ..r]}(z) = \max \{ \theta ^{i, -, h}(z) \mid h \in [\ell ..r]\}. \end{aligned}$$

Algorithm for computing $\mathsf {OPT}(i,j)$ for given $i,j \in [1..n]$ with $i < j$

Phase 1::

Find a set U of the maximal subpath nodes for $P_{{i+1},{j-1}}$ by walking on segment tree ${\mathcal {T}}$ from leaf $i+1$ to leaf $j-1$.

Phase 2::

For each $u \in U$, compute a real interval ${{\mathcal {I}}}^+_u$ such that $\theta ^{i,+}(z) = \theta ^{i,+,[\ell _u..r_u]}(z)$ holds on any $z \in {{\mathcal {I}}}^+_u$, and a real interval ${{\mathcal {I}}}^-_u$ such that $\theta ^{j,-}(z) = \theta ^{j,-,[\ell _u..r_u]}(z)$ holds on any $z \in {{\mathcal {I}}}^-_u$, both of which are obtained by using information stored at node u. See Sect. 5.1 in  [14] for the details.

Phase 3::

Compute the pseudo-intersection point $z^*$ of $\theta ^{i,+}(z)$ and $\theta ^{j,-}(z)$ on $[W_i,W_{j-1}]$ by using real intervals obtained in Phase 2. See Sect. 5.2 in  [14] for the details.

Phase 4::

Compute $\mathsf {OPT}(i,j) = \varPhi ^{i,j}(z^*)$ as follows: By formula (7), we have

$$\begin{aligned} \varPhi ^{i,j}(z^*)= & {} \int _{0}^{z^*} \theta ^{i, +}(t)dt + \int _{z^*}^{W_n} \theta ^{j, -}(t)dt \\= & {} \sum _{u \in U}\left\{ \int _{{{\mathcal {I}}}^+_u \cap [0, z^*]} \theta ^{i, +, [\ell _u..r_u]}(t)dt + \int _{{{\mathcal {I}}}^-_u \cap [z^*, W_n]} \theta ^{j, -, [\ell _u..r_u]}(t)dt \right\} . \end{aligned}$$

For each $u \in U$, we compute integrals $\int \theta ^{i, +, [\ell _u..r_u]}(t)dt$ and $\int \theta ^{j, -, [\ell _u..r_u]}(t)dt$ by using the information stored at u. See Sect. 5.3 in  [14] for the details.

For the cases of $i=0$ or $j=n+1$, we can also compute $w'(0,j) = \varPhi ^{j, -}(0)$ and $w'(i,n+1) = \varPhi ^{i, +}(W_n)$ by the same operations except for Phase 3.

We give the following lemma about the running time of the above algorithm for the case of general edge capacities. See Lemma 8 in  [14] for the proof.

Lemma 5

(Key lemma for general capacity). Let us suppose that a segment tree ${\mathcal {T}}$ is available. Given two integers $i,j \in [0..n+1]$ with $i<j$, one can compute a value $w'(i,j)$ in $O(\log ^3 n)$ time for the confluent/non-confluent flow model.

Recalling that the running time for construction of data structure ${\mathcal {T}}$ is $O(n \log ^2 n)$, Lemmas 3, 4 and 5 imply the following main theorem.

Theorem 1

(Main theorem for general capacity). Given a dynamic flow path network $\mathcal {P}$, there exists an algorithm that finds an optimal k-sink under the confluent/non-confluent flow model in time $\min \{ O(kn\log ^3n),n 2^{O(\sqrt{\log k \log \log n})}$ $\log ^3n \}$.

When the capacities of ${{\mathcal {P}}}$ are uniform, we can improve the running time for computing $w'(i,j)$ to $O(\log ^2 n)$ time with minor modification. See Lemma 9 in  [14] for the proof.

Lemma 6

(Key lemma for uniform capacity). Let us suppose that a segment tree ${\mathcal {T}}$ is available. Given two integers $i,j \in [1..n]$ with $i<j$, one can compute a value $w'(i,j)$ in $O(\log ^2 n)$ time for the confluent/non-confluent flow model when the capacities are uniform.

Theorem 2

(Main theorem for uniform capacity). Given a dynamic flow path network $\mathcal {P}$ with a uniform capacity, there exists an algorithm that finds an optimal k-sink under the confluent/non-confluent flow model in time $\min \{ O(kn\log ^2n), n 2^{O(\sqrt{\log k \log \log n})} \log ^2n \}$.

4 Data Structures Associated with Nodes of ${\mathcal {T}}$

In the rest of the paper, we introduce novel data structures associated with each node u of segment tree ${\mathcal {T}}$, which are used to compute $\mathsf {OPT}(i,j)$ in $O(\mathrm{poly}\log n)$ time. Note that our data structures generalize the capacities and upper envelopes tree (CUE tree) provided by Bhattacharya et al.  [7].

Recall the algorithm for computing $\mathsf {OPT}(i,j)$ shown in Sect. 3. To explain the data structures, let us see more precisely how the algorithm performs in Phase 2. Confirm that for $z \in [W_i, W_{j-1}]$, it holds $\theta ^{i,+}(z) = \max \{\theta ^{i,+,[\ell _u..r_u]}(z) \mid u \in U\}$, where U is a set of the maximal subpath nodes for $P_{{i+1},{j-1}}$. Let us focus on function $\theta ^{i,+,[\ell _u..r_u]}(z)$ for a node $u \in U$ only on interval $(W_{\ell _u-1},W_n]$ since it holds $\theta ^{i,+,[\ell _u..r_u]}(z)=0$ if $z \le W_{\ell _u-1}$. Interval $(W_{\ell _u-1},W_n]$ consists of three left-open-right-closed intervals ${\mathcal {J}}^{+}_{u,1}$, ${\mathcal {J}}^{+}_{u,2}$ and ${\mathcal {J}}^{+}_{u,3}$ that satisfy the following conditions: (i) For $z \in {\mathcal {J}}^{+}_{u,1}$, $\theta ^{i,+,[\ell _u..r_u]}(z)=\theta ^{i,+,\ell _u}(z)$. (ii) For $z \in {\mathcal {J}}^{+}_{u,2}$, $\theta ^{i,+,[\ell _u..r_u]}(z)=\theta ^{i,+,[\ell _u+1..r_u]}(z)$ and its slope is $1/{C_{i,\ell _u}}$. (iii) For $z \in {\mathcal {J}}^{+}_{u,3}$, $\theta ^{i,+,[\ell _u..r_u]}(z)=\theta ^{i,+,[\ell _u+1..r_u]}(z)$ and its slope is greater than $1/{C_{i,\ell _u}}$. See also Fig. 2. Thus in Phase 2, the algorithm computes ${\mathcal {J}}^{+}_{u,1}$, ${\mathcal {J}}^{+}_{u,2}$ and ${\mathcal {J}}^{+}_{u,3}$ for all $u \in U$, and combines them one by one to obtain intervals ${{\mathcal {I}}}^+_u$ for all $u \in U$. To implement these operations efficiently, we construct some data structures at each node u of ${\mathcal {T}}$. To explain the data structures stored at u, we introduce the following definition:

Definition 3

For integers $i,\ell ,r \in [1..n]$ with $i < \ell \le r$ and a positive real c, let $\bar{\theta }^{i, +, [\ell ..r]}(c,z) = \max \{ \bar{\theta }^{i, +, h}(c,z) \mid h \in [\ell ..r]\}$, where

$$\begin{aligned} \bar{\theta }^{i,+,j}(c, z) = \left\{ \begin{array}{ll} 0 &{} \text {if } z \le W_{j-1}, \\ \frac{z - W_{j-1}}{c} + \tau \cdot L_{i,j} &{} \text {if } z > W_{j-1}. \end{array} \right. \end{aligned}$$

(10)

For integers $i,\ell ,r \in [1..n]$ with $\ell \le r < i$ and a positive real c, let $\bar{\theta }^{i, -, [\ell ..r]}(c,z) = \max \{ \bar{\theta }^{i, -, h}(c,z) \mid h \in [\ell ..r]\}$, where

$$\begin{aligned} \bar{\theta }^{i,-,j}(c, z) = \left\{ \begin{array}{ll} \frac{W_{j} - z}{c} + \tau \cdot L_{j,i} &{} \text {if } z < W_j, \\ 0 &{} \text {if } z \ge W_j. \end{array} \right. \end{aligned}$$

(11)

We can see that for $z \in {\mathcal {J}}^{+}_{u,2}$, $\theta ^{i,+,[\ell _u+1..r_u]}(z)=\bar{\theta }^{\ell _u, +, [\ell _u+1..r_u]}(C_{i,\ell _u},z)+\tau \cdot L_{i,\ell _u}$, and for $z \in {\mathcal {J}}^{+}_{u,3}$, $\theta ^{i,+,[\ell _u+1..r_u]}(z)=\theta ^{\ell _u,+,[\ell _u+1..r_u]}(z)+\tau \cdot L_{i,\ell _u}$. We then store at u of ${\mathcal {T}}$ the information for computing in $O(\mathrm{poly}\log n)$ time $\theta ^{\ell _u,+,[\ell _u+1..r_u]}(z)$ for any $z \in [0,W_n]$ as TYPE I, and also one for computing in $O(\mathrm{poly}\log n)$ time $\bar{\theta }^{\ell _u,+,[\ell _u+1..r_u]}(c, z)$ for any $c>0$ and any $z \in [0,W_n]$ as TYPE III.

Fig. 2.

Illustration of ${\mathcal {J}}^{+}_{u,1}$, ${\mathcal {J}}^{+}_{u,2}$ and ${\mathcal {J}}^{+}_{u,3}$. The thick half lines have the same slope of $1/C_{i,\ell _u}$, the gray half lines have slopes $\le 1/C_{i,\ell _u}$, and the regular half lines have slopes $>1/C_{i,\ell _u}$. The upper envelope of all the thick half lines and the regular half lines is function $\theta ^{i,+,[\ell _u..r_u]}(z)$.

In Phase 4, the algorithm requires computing integrals $\int _0^z \theta ^{\ell _u, +, [\ell _u+1.. r_u]}(t)dt$ for any $z \in [0,W_n]$, and $\int _0^z \bar{\theta }^{\ell _u,+,[\ell _u+1..r_u]}(c, t) dt$ for any $c>0$ and any $z \in [0,W_n]$, for which the information is stored at each $u \in {\mathcal {T}}$ as TYPEs II and IV, respectively.

In a symmetric manner, we also store at each $u \in {\mathcal {T}}$ the information for computing $\theta ^{r_u, -, [\ell _u.. r_u-1]}(z)$, $\int _z^{W_n} \theta ^{r_u, -, [\ell _u.. r_u-1]}(t)dt$, $\bar{\theta }^{r_u,-, [\ell _u.. r_u-1]}(c, z)$, and $\int _z^{W_n}\bar{\theta }^{r_u,-,[\ell _u..r_u-1]}(c, t)dt$ as TYPEs I, II, III, and IV, respectively.

Let us introduce what information is stored as TYPEs I–IV at $u \in {\mathcal {T}}$. See Sect. 4 in  [14] for the detail.

TYPE I. We give the information only for computing $\theta ^{\ell _u,+,[\ell _u+1..r_u]}(z)$ stored at $u \in {\mathcal {T}}$ as TYPE I since the case for $\theta ^{r_u, -, [\ell _u..r_u-1]}(z)$ is symmetric. By Definition 2, the function $\theta ^{\ell _u, +, [\ell _u+1.. r_u]}(z)$ is the upper envelope of $m_u$ functions $\theta ^{\ell _u, +, h}(z)$ for $h \in [\ell _u+1..r_u]$. Let ${\mathcal {B}}^{u,+} = (b^{u,+}_1 = 0, b^{u,+}_2, \ldots , b^{u,+}_{N^{u,+}} = W_n)$ denote a sequence of breakpoints of $\theta ^{\ell _u, +, [\ell _u+1.. r_u]}(z)$, where $N^{u,+}$ is the number of breakpoints. For each $p \in [1..N^{u,+} - 1]$, let $H^{u,+}_p \in [\ell _u+1..r_u]$ such that $\theta ^{\ell _u, +, [\ell _u+1.. r_u]}(z)=\theta ^{\ell _u, +, H^{u,+}_p}(z)$ holds for any $z \in (b^{u,+}_{p}, b^{u,+}_{p+1}]$. As TYPE I, each node $u \in {\mathcal {T}}$ is associated with following two lists:

• 1. Pairs of breakpoint $b^{u,+}_p$ and value $\theta ^{\ell _u, +, [\ell _u+1.. r_u]}(b^{u,+}_p)$, and

• 2. Pairs of range $(b^{u,+}_{p}, b^{u,+}_{p+1}]$ and index $H^{u,+}_p$.

Note that the above lists can be constructed in $O(m_u \log m_u)$ time for each $u \in {\mathcal {T}}$. By Property 2, we can obtain the whole information of TYPE I of ${\mathcal {T}}$ in time $O(n\log ^2 n)$. We now give the application of TYPE I. See Lemma 11 in  [14] for the proof.

Lemma 7

(Query with TYPE I). Suppose that TYPE I of ${\mathcal {T}}$ is available. Given a node $u \in {\mathcal {T}}$ and a real value $z \in [0,W_n]$, we can obtain

• (i) index $H \in [\ell _u+1..r_u]$ such that $\theta ^{\ell _u, +, H}(z) = \theta ^{\ell _u,+,[\ell _u+1.. r_u]}(z)$, and

• (ii) index $H \in [\ell _u..r_u-1]$ such that $\theta ^{r_u, -, H}(z) = \theta ^{r_u, -, [\ell _u.. r_u-1]}(z)$

in time $O(\log n)$ respectively. Furthermore, if the capacities of $\mathcal {P}$ are uniform and $z \notin [W_{\ell _u},W_{r_u-1}]$, we can obtain the above indices in time O(1).

TYPE II. We give the information only for computing $\int _0^z \theta ^{\ell _u, +, [\ell _u+1.. r_u]}(t)dt$ stored at $u \in {\mathcal {T}}$ as TYPE II since the case for $\int _z^{W_n} \theta ^{r_u, -, [\ell _u.. r_u-1]}(t)dt$ is symmetric. Each node $u \in {\mathcal {T}}$ contains a list of all pairs of breakpoint $b^{u,+}_p$ and value $\int _{0}^{b^{u,+}_p}\theta ^{\ell _u, +, [\ell _u+1.. r_u]}(t)dt$. This list can be constructed in $O(m_u)$ time for each $u \in {\mathcal {T}}$ by using TYPE I of u. By Property 2, we obtain the whole information of TYPE II of ${\mathcal {T}}$ in time $O(n\log n)$. We give the application of TYPEs I and II. See Lemma 12 in  [14] for the proof.

Lemma 8

(Query with TYPEs I and II). Suppose that TYPEs I and II of ${\mathcal {T}}$ is available. Given a node $u \in {\mathcal {T}}$ and a real value $z \in [0,W_n]$, we can obtain

(i) value $\int _{0}^{z} \theta ^{\ell _u, +, [\ell _u+1.. r_u]}(t)dt$, and (ii) value $\int _{z}^{W_n} \theta ^{r_u, -, [\ell _u.. r_u-1]}(t)dt$ in time $O(\log n)$ respectively. Furthermore, if the capacities of $\mathcal {P}$ are uniform and $z \notin [W_{\ell _u},W_{r_u-1}]$, we can obtain the above values in time O(1).

TYPE III. We give the information only for computing $\bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, z)$ stored at $u \in {\mathcal {T}}$ as TYPE III since the case for $\bar{\theta }^{r_u,-, [\ell _u.. r_u-1]}(c, z)$ is symmetric. Note that it is enough to prepare for the case of $z \in (W_{\ell _u},W_{r_u}]$ since it holds that $\bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, z) = 0$ for $z \in [0, W_{\ell _u}]$ and

$$\begin{aligned} \bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, z) = \bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, W_{r_u}) + \frac{z-W_{r_u}}{c} \end{aligned}$$

for $z \in (W_{r_u}, W_n]$, of which the first term is obtained by prepared information with $z = W_{r_u}$ and the second term is obtained by elementally calculation.

For each $u \in {\mathcal {T}}$, we construct a persistent segment tree as TYPE III. Referring to formula (10), each function $\bar{\theta }^{\ell _u,+,j}(c, z)$ for $j \in [l_u+1..r_u]$ is linear in $z \in (W_{j-1},W_n]$ with the same slope 1/c. Let us make parameter c decrease from $\infty$ to 0, then all the slopes 1/c increase from 0 to $\infty$. As c decreases, the number of subfunctions that consist of $\bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, z)$ also decreases one by one from $m_u$ to 1. Let $c^{u,+}_{h}$ be a value c at which the number of subfunctions of $\bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, z)$ becomes $m_u-h$ while c decreases. Note that we have $\infty = c^{u,+}_{0}> c^{u,+}_{1}> \cdots> c^{u,+}_{m_u-1} > 0$. Let us define indices $j^{h}_1, \ldots , j^{h}_{m_u-h}$ with $l_u+1 = j^h_1< \cdots < j^h_{m_u-h} \le r_u$ corresponding to the subfunctions of $\bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c^{u,+}_{h}, z)$, that is, for any integer $p \in [1..m_u-h]$, we have

$$\begin{aligned} \bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c^{u,+}_{h}, z) = \bar{\theta }^{\ell _u,+,j^h_p}(c^{u,+}_{h}, z) \quad \text {if} \ z \in (W_{j^{h}_p-1},W_{j^{h}_{p+1}-1}], \end{aligned}$$

(12)

where $j^{h}_{m_u-h+1}-1={r_u}$. We give the following lemma about the property of $c^{u,+}_{h}$. See Lemma 13 in  [14] for the proof.

Lemma 9

For each node $u \in {\mathcal {T}}$, all values $c^{u,+}_{1}, \ldots , c^{u,+}_{m_u-1}$ can be computed in $O(m_u \log m_u)$ time.

By the above argument, while $c \in (c^{u,+}_{h},c^{u,+}_{h-1}]$ with some $h \in [1..m_u]$ (where $c^{u,+}_{m_u}=0$), the representation of $\bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, z)$ (with $m_u-h+1$ subfunctions) remains the same. Our fundamental idea is to consider segment trees corresponding to each interval $(c^{u,+}_{h},c^{u,+}_{h-1}]$ with $h \in [1..m_u]$, and construct a persistent data structure for such the segment trees.

First of all, we introduce a segment tree $T_h$ with root $\rho _h$ to compute $\bar{\theta }^{\ell _u, +,[\ell _u+1.. r_u]}(c, z)$ for $c \in (c^{u,+}_{h},c^{u,+}_{h-1}]$ with $h \in [1..m_u]$. Tree $T_h$ contains $m_u$ leaves labeled as $l_u+1, \ldots , r_u$. Each leaf j corresponds to interval $(W_{j-1}, W_{j}]$. For a node $\nu \in T_h$, let $\ell _{\nu }$ (resp. $r_{\nu }$) denote the label of the leftmost (resp. rightmost) leaf of the subtree rooted at ${\nu }$. Let $p_{\nu }$ denote the parent of $\nu$ if $\nu \ne \rho _h$. We say a node $\nu \in T_h$ spans an interval $(W_{\ell _{\nu }-1}, W_{r_{\nu }}]$. For some two integers $i,j \in [\ell _u+1..r_u]$ with $i<j$, if $(W_{\ell _{\nu }-1}, W_{r_{\nu }}] \subseteq (W_{i-1}, W_j]$ and $(W_{\ell _{p_{\nu }-1}}, W_{r_{p_{\nu }}}] \not \subseteq (W_{i-1}, W_j]$, then $\nu$ is called a maximal subinterval node for $(W_{i-1}, W_j]$. A segment tree $T_h$ satisfies the following property similar to Property 1: For any two integers $i,j \in [\ell _u+1..r_u]$ with $i<j$, the number of maximal subinterval nodes in $T_h$ for $(W_{i-1}, W_j]$ is $O(\log m_u)$. For each $p \in [1..m_u-h+1]$, we store function $\bar{\theta }^{\ell _u,+,j^{h-1}_p}(c, z)$ at all the maximal subinterval nodes for interval $(W_{j^{h-1}_p-1}, W_{j^{h-1}_{p+1}-1}]$, which takes $O(m_u\log m_u)$ time by the property. The other nodes in $T_h$ contains NULL.

If we have $T_h$, for given $z \in (W_{\ell _u},W_{r_u}]$ and $c \in (c^{u,+}_{h},c^{u,+}_{h-1}]$, we can compute value $\bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, z)$ in time $O(\log m_u)$ as follows: Starting from root $\rho _h$, go down to a child such that its spanned interval contains z until we achieve a node that contains some function $\bar{\theta }^{\ell _u,+,j}(c, z)$ (not NULL). Now, we know $\bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, z) = \bar{\theta }^{\ell _u,+,j}(c, z)$, which can be computed by elementally calculation.

If we explicitly construct $T_h$ for all $h \in [1..m_u]$, it takes $O(m_u^2\log m_u)$ time for each node $u \in {\mathcal {T}}$, which implies by Property 2 that $O(n^2\log ^2 n)$ time is required in total. However, using the fact that $T_h$ and $T_{h+1}$ are almost same except for at most $O(\log m_u)$ nodes, we can construct a persistent segment tree in $O(m_u\log m_u)$ time, in which we can search as if all of $T_h$ are maintained. Thus, we obtain the whole information of TYPE III of ${\mathcal {T}}$ in time $O(n \log ^2 n)$ by Property 2.

Using this persistent segment tree, we can compute $\bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, z)$ for any $z \in [0,W_n]$ and any $c>0$ in $O(\log m_u)$ time as follows: Find integer h over $[1..m_u]$ such that $c \in (c^{u,+}_{h},c^{u,+}_{h-1}]$ in $O(\log m_u)$ time by binary search, and then search in the persistent segment tree as $T_{h}$ in time $O(\log m_u)$.

Lemma 10

(Query with TYPE III). Suppose that TYPE III of ${\mathcal {T}}$ is available. Given a node $u \in {\mathcal {T}}$, real values $z \in [0, W_n]$ and $c>0$, we can obtain

• (i) index $H \in [\ell _u+1..r_u]$ such that $\bar{\theta }^{\ell _u,+,H}(c, z) = \bar{\theta }^{\ell _u, +,[\ell _u+1.. r_u]}(c, z)$, and

• (ii) index $H \in [\ell _u..r_u-1]$ such that $\bar{\theta }^{r_u,-,H}(c, z) = \bar{\theta }^{r_u,-,[\ell _u.. r_u-1]}(c, z)$ in time $O(\log n)$ respectively.

TYPE IV. We give the information only for computing $\int ^z_0 \bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, t)dt$ stored at $u \in {\mathcal {T}}$ as TYPE IV since the case for $\int ^{W_n}_z \bar{\theta }^{\ell _u,-,[\ell _u.. r_u-1]}(c, t)dt$ is symmetric. Similar to TYPE III, we prepare only for the case of $z \in (W_{\ell _u},W_{r_u}]$ since it holds that $\int ^z_0 \bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, t)dt = 0$ for $z \in [0, W_{\ell _u}]$ and

$$\begin{aligned} \int ^z_0 \bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, t)dt = \int ^{W_{r_u}}_0 \bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, t)dt + \frac{(z - W_{r_u})^2}{2c} \end{aligned}$$

for $z \in (W_{r_u}, W_n]$, of which the first term can be obtained by prepared information with $z = W_{r_u}$ and the second term by elementally calculation.

For each $u \in {\mathcal {T}}$, we construct a persistent segment tree again, which is similar to one shown in the previous section. To begin with, consider the case of $c \in (c^{u,+}_{h},c^{u,+}_{h-1}]$ with some $h \in [1..m_u]$ (where recall that $c^{u,+}_{0} = \infty$ and $c^{u,+}_{m_u} = 0$), and indices $j^{h-1}_1, \cdots , j^{h-1}_{m_u-h+1}$ that satisfy (12). In this case, for $z \in (W_{j^{h-1}_p-1}, W_{j^{h-1}_{p+1}-1}]$ with $p \in [1..m_u-h+1]$, we have

$$\begin{aligned} \int ^z_0 \bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, t)dt = \sum _{q=1}^{p-1} \left\{ \int _{W_{j^{h-1}_q-1}}^{W_{j^{h-1}_{q+1}-1}} \bar{\theta }^{\ell _u,+,j^{h-1}_q}(c, t)dt \right\} + \int _{W_{j^{h-1}_p-1}}^{z} \bar{\theta }^{\ell _u,+,j^{h-1}_p}(c, t)dt. \end{aligned}$$

(13)

For ease of reference, we use $F^{h,p}(c,z)$ instead of the right hand side of (13).

Similarly to the explanation for TYPE III, let $T_h$ be a segment tree with root $\rho _h$ and $m_u$ leaves labeled as $l_u+1, \ldots , r_u$, and each leaf j of $T_h$ corresponds to interval $(W_{j-1}, W_{j}]$. In the same manner as for TYPE III, for each $p \in [1..m_u-h+1]$, we store function $F^{h,p}(c,z)$ at all the maximal subinterval nodes in $T_h$ for interval $(W_{j^{h-1}_p-1}, W_{j^{h-1}_{p+1}-1}]$. Using $T_h$, for any $z \in (W_{\ell _u},W_{r_u}]$ and any $c \in (c^{u,+}_{h},c^{u,+}_{h-1}]$, we can compute value $\int ^z_0 \bar{\theta }^{\ell _u,+,[\ell _u+1.. r_u]}(c, t)dt$ in time $O(\log m_u)$ by summing up all functions of nodes on a path from root $\rho _h$ to leaf with an interval that contains z. Actually, we store functions in a more complicated way in order to maintain them as a persistent data structure. We construct a persistent segment tree at $u \in {\mathcal {T}}$ in $O(m_u\log m_u)$ time, in which we can search as if all of $T_h$ are maintained. Using this persistent segment tree, we can compute $\int _{0}^{z} \bar{\theta }^{\ell _u, +, [\ell _u+1.. r_u]}(c,t)dt$ for any $z \in [0,W_n]$ and any $c >0$ in $O(\log m_u)$ time in the same manner as for TYPE III.

Lemma 11

(Query with TYPE IV). Suppose that TYPE IV of ${\mathcal {T}}$ is available. Given a node $u \in {\mathcal {T}}$, real values $z \in [0, W_n]$ and $c>0$, we can obtain (i) value $\int _{0}^{z} \bar{\theta }^{\ell _u, +, [\ell _u+1.. r_u]}(c,t)dt$, and (ii) value $\int _{z}^{W_n} \bar{\theta }^{r_u, -, [\ell _u.. r_u-1]}(c,t)dt$ in time $O(\log n)$ respectively.

5 Conclusion

We remark here that our algorithms can be extended to the minsum k-sink problem in a dynamic flow path network, in which each vertex $v_i$ has the cost $\lambda _i$ for locating a sink at $v_i$, and we minimize $\mathsf {AT}(\mathcal {P}, \mathbf{x}, \mathbf{d})+\sum _i \{\lambda _i \mid \mathbf{x}\,\text {consists of}\,v_i\}$. Then, the same reduction works with link costs $w''(i,j)=w'(i,j)+\lambda _i$, which still satisfy the concave Monge property. This implies that our approach immediately gives algorithms of the same running time.