Document [original]

Continuous and discrete flows over time

A general model based on measure theory

Ronald Koch ·Ebrahim Nasrabadi ·Martin

Skutella

Abstract Network flows over time form a fascinating area of research. They model

the temporal dynamics of network flow problems occurring in a wide variety of applica-

tions. Research in this area has been pursued in two different and mainly independent

directions with respect to time modeling: discrete and continuous time models.

In this paper we deploy measure theory in order to introduce a general model of

network flows over time combining both discrete and continuous aspects into a single

model. Here, the flow on each arc is modeled as a Borel measure on the real line (time

axis) which assigns to each suitable subset a real value, interpreted as the amount

of flow entering the arc over the subset. We focus on the maximum flow problem

formulated in a network where capacities on arcs are also given as Borel measures and

storage might be allowed at the nodes of the network. We generalize the concept of cuts

to the case of these Borel Flows and extend the famous MaxFlow-MinCut Theorem.

Keywords Network Flows ·Flows Over Time ·Measure Theory ·MaxFlow-MinCut

1 Introduction

Network flows over time (also called dynamic flows in the literature) are an interesting

and challenging area of research. In contrast to classical static flows, they include a

temporal dimension and consequently provide a more realistic modeling tool for a wide

variety of applications. In general, there are two aspects which distinguish flows over

time from static flows. Firstly, flow values on arcs are not constant but may change

over time due to seasonally altering demands, supplies, and arc capacities. Secondly,

flow does not travel instantaneously through a network but requires a certain amount

of time to travel through each arc.

The notion of flows over time was first introduced by Ford and Fulkerson [7,8]. They

study the maximum flow over time problem where the aim is to find the maximum

This work is supported by DFG project SK58/7-1.

This work is a revised version of 2010.

The first and third author are supported by the DFG Research Center Matheon in Berlin.

Technische Universit¨at Berlin, Institut f¨ur Mathematik, Straße des 17. Juni 136, 10623

Berlin, Germany, phone: +49 (0)30 314-28641, fax: +49 (0)30 314-25191, E-mail:

{koch,nasrabadi,skutella}@math.tu-berlin.de

amount of flow that can be sent from a source node to a sink node within a given

time horizon. Ford and Fulkerson show that this problem can be solved efficiently by

one minimum cost flow computation on the given network, where transit times of arcs

are interpreted as arc costs. Since then, flows over time have become an area of active

research and many authors have extensively studied different features of flows over

time (see, e.g., [4,10–12,17,18] and the references therein).

In the model studied by Ford and Fulkerson, time is measured in discrete time

steps and arc capacities are time independent. In contrast to this, Philpott [14] and

Anderson, Nash, and Philpott [2] study the maximum flow over time problem in a

network with zero transit times and time-varying transit and storage capacities for the

case where time is modeled as a continuum. They extend the concept of cuts to their

continuous-time setting and establish a MaxFlow-MinCut theorem (see also [1]). This

result was later extended by Philpott [15] to arbitrary transit times on the arcs.

For the case in which the network parameters (e.g., costs, capacities, supplies, and

demands) are independent of time, and transit times on arcs as well as the time horizon

are integral, Fleischer and Tardos [6] point out a close correspondence between discrete

and continuous flows over time. In fact, in this case every continuous flow over time

problem can be formulated and solved as a discrete flow over time problem. Fleischer

and Tardos [6] show how a number of results and algorithms for the discrete time model

can be carried over to the analogous continuous-time model, even if the time horizon

is not integral. These results do not remain true for the more general setting where

network parameters are subject to fluctuation over time.

Both discrete and continuous models have their advantages and disadvantages.

Discrete flow over time problems are considerably easier to solve computationally, but

they suffer from a serious drawback: the times at which decisions are being made are

fixed in advance before the problem is solved. For many applications, this is by no

means a necessary feature of the problem. This is where the continuous-time model

comes into play allowing decisions to be made at arbitrary points in time. Although this

approach is, in theory, suitable to model various applications such as pipeline systems

for transportation (e.g., the problem of pumping water through a water distribution

network), it fails to capture the discrete nature of typical applications such as vehicle

routing and scheduling (e.g., the scheduling of trains in a railway network).

Contribution of the paper. A precise description of many real-world problems requires

a combination of discrete- and continuous-time models. One such example is a crude

oil distribution system. There are several methods that are used to transport crude oil:

pipelines, tank trucks, railroad tank cars, barges, and tankers. Here, pumping crude oil

into pipes naturally requires a continuous time model, whereas scheduling the transport

of crude oil by tank trucks, railroad tank cars, barges, and tankers must be done in a

discrete time model. As a consequence, it is worthwhile to capture both discrete and

continuous aspects of real-world scenarios by means of a single model. Our approach

is based on measure theory. The flow on each arc is modeled as a measure on the real

line (time axis) which assigns to each suitable subset a real value, interpreted as the

amount of flow entering the arc over the subset. We thus extend the notion of flows

over time from the viewpoint of measure theory.

This approach is novel and has, to the best of our knowledge, never been pursued

in the network flow literature so far. The only work taking a similar approach is by

Philpott [16] who studies the continuous-time shortest path problem. This problem is

an extension of the shortest path problem to networks with time-dependent arc costs.

Moreover, each arc has a fixed transit time and waiting at the nodes of the network is

allowed but causes a time-dependent cost. Philpott [16] formulates the problem as a

linear program in the space of finite Borel measures over R, introduces a dual program,

and proves various structural results including strong duality for the case where the

cost functions are all Lipschitz-continuous.

In this paper we study the maximum flow over time problem formulated on a

directed network where the flow on each arc is a Borel measure on Rand storage might

be allowed at the nodes of the network. Flow on arcs and storage of flow at nodes are

subject to upper bounds given by Borel measures and right-continuous functions of

bounded variation, respectively. We establish a MaxFlow-MinCut Theorem under the

assumption that the arc capacities are finite Borel measures. While the basic idea is

the same as in the proof of the corresponding theorem for the static case, our general

measure-based definition of flows over time imposes quite a few complications and

interesting challenges. We generalize the definition of cuts and their capacities as well as

the concept of residual networks and reachable nodes to these Borel flows. It turns out

that, in order to make this generalization work, a number of new ideas and techniques

are required; an illustrative description of one particular problem occurring in this

process is, for example, given at the beginning of Section 6 in Examples 1, 2, and 3.

Outline. The paper is organized as follows. We begin our discussion in Section 2 by

briefly describing flows over time in a discrete and continuous model. We then explain

how these two models can be combined into a single model by using measures and

introduce the notion of Borel flows. In Section 3, we formulate the maximum Borel

flow problem as an infinite-dimensional linear program and prove the existence of a

maximum Borel flow.

Section 4 is devoted to the definition of Borel cuts and their capacities. A Borel cut

is defined by assigning a Borel set to each node, containing the points in time when the

node belongs to the source side of the cut. It is shown that the capacity of any Borel

cut is an upper bound on the value of each Borel flow.

In Section 5 we define the residual network with respect to a Borel flow. Afterwards,

in Section 6, it is shown that the value of a Borel flow can be improved if the sink is

reachable from the source in the residual network. To this end, a procedure is presented

to compute, for each node, the points in time at which the node is reachable from the

source. In general, this procedure is not an algorithm for actual computation, but rather

gives a definition for the set of the points in time at which flow can reach a node.

In Section 7 we show that the procedure of Section 5 yields a Borel cut whose

capacity equals the value of a maximum Borel flow if it is applied to the residual

network of a maximum Borel flow. This constitutes the main result of the paper.

In Section 8 we discuss several promising directions for future research. In Ap-

pendix A we briefly review the definitions and results from the area of measure theory

which we use in this paper. We suggest that readers who are not familiar with measure

theory first read Appendix A in order to follow the paper. In Appendix B we prove

some technical lemmas.

2 Borel flows

We consider a directed graph G= (V, E) with finite node set Vand finite arc set E.

A single commodity must be routed through Gfrom a source s∈Vto a sink t∈V.

We assume that there is an s-v-path and a v-t-path in Gfor every node v∈V.

This assumption imposes no loss of generality since nodes which are not contained in

any s-tpath are useless for routing flow from sto tand can therefore be deleted. An

arc e∈Efrom a node vto a node wis denoted by e:= (v, w). In this case, we say that

node vis the tail of eand wis the head of e, and write tail(e) := vand head(e) := w.

Each arc e∈Ehas an associated transit time τe∈Rspecifying the required amount of

time for traveling from the tail to the head of e. More precisely, if flow leaves node vat

time θalong an arc e= (v, w), it arrives at wat time θ+τe. Note that the transit times

are not necessarily nonnegative. One particular reason is that we also consider flows in

the residual network (see Section 5) and in general, the residual network contains arcs

with negative transit times.

In general, the research on flows over time has pursued two main approaches with

respect to time modeling, namely discrete and continuous time models. In the discrete

model, time is discretized into intervals of unit length. For integral transit times (τe)e∈E

and an integral time horizon T, a discrete flow over time is defined by a function

xe:{0,1,2, . . . , T −1} −→ R≥0,

for each arc e∈E. Here, the value xe(θ) denotes the amount of flow which is sent at

time θinto arc eand arriving at the head of eat time θ+τe. In contrast, a continuous

flow over time consists of a Lebesgue integrable function

xe: [0, T )−→ R≥0,

for each arc e∈E. Here, the value xe(θ) represents the rate at which flow enters arc e

at time θ.

In what follows we make use of measure theory and introduce a new model of flows

over time that encompasses both the discrete and the continuous model. To simplify

notation, we consider the entire real line Rinstead of the time interval [0, T ) and set

the initial time to −∞ and the final time to ∞. This is, of course, no restriction since

any maximum flow over time problem with time horizon Tcan be considered on Rby

letting all arc capacities be zero outside the interval [0, T ). In order to motivate the

use of measure theory, we first let Bbe the collection of all intervals in R. In order to

describe the flow over time on each arc e∈E, we assign a value xe(I) to each time

interval Iindicating the amount of flow entering arc eover the time interval I. Thus,

intuitively, the function xe:B → Rhas to satisfy the following properties:

(i) The flow assigned to the empty set is 0, i.e., xe(∅) = 0.

(ii) An amount of flow is always nonnegative, i.e., xe(I)≥0 for all I∈ B.

(iii) For a countable collection (Ii)i∈Nof pairwise disjoint intervals in B, it holds that

xe[

i∈N

Ii=X

i∈N

xe(Ii).

On closer inspection of property (iii) we observe that Bmust be closed under

countable unions. Otherwise this property is not well defined. In addition we require

that Bis also closed under complement. Therefore we extend the definition of Bto

the smallest set containing all (open) intervals which is closed under complements

and countable unions. Hence Bis the Borel σ-algebra on Rand a member B∈ B is

called a Borel set or measurable set. In this manner properties (i)–(iii) make xeto a

Borel measure over R. Thus, measure theory provides a realistic and adequate tool for

modeling flow distributions over time.

Following the above observations, a Borel flow xis defined by a family of Borel

measures

xe:B −→ R∀e∈E .

Here, the value xe(B) gives the amount of flow entering arc eover the Borel set B.

Moreover, with each arc e∈Ewe associate a Borel measure ue:B → R≥0which

denotes its capacity. That is, ue(B) is an upper bound on the amount of flow that is

able to enter arc eover the Borel set B. We require that a Borel flow xfulfills arc

capacity constraints

xe(B)≤ue(B)∀e∈E, B ∈ B .

The flow xinduces a storage function Yvon Rat each node vby the following flow

conservation constraint

Yv(θ) := X

e∈δ−(v)

xe(−∞, θ −τe]−X

e∈δ+(v)

xe(−∞, θ]∀θ∈R.(1)

Here and throughout the rest of the paper, δ+(v) and δ−(v) are used to denote the

sets of arcs leaving node vand entering node v, respectively. Note that Yvis the

difference between two right continuous, monotonic increasing functions and thus is

a right continuous function of bounded variation. In (1), the first sum represents the

total amount of flow arriving at node vup to time θ. Analogously, the second sum

represents the total amount of flow leaving node vup to time θ. Thus, the value Yv(θ)

gives the amount of flow stored at node vat the point in time θ. Flow originates at

the source sand terminates at the sink t. Thus we must have

Ys(θ)≤0 and Yt(θ)≥0∀θ∈R.

We suppose that the storage of flow at a node v∈Vis bounded from above by

a function Uv:R→R≥0. The value Uv(θ) is an upper bound on the amount of flow

that can be stored at node vat time θ. We assume that Uvis of bounded variation and

continuous from the right for each node v. This imposes no restriction since Yvis a

right continuous function of bounded variation. Further, with each node v∈V\ {s, t}

we also associate a right continuous function Lv:R→R≥0of bounded variation.

The value −Lv(θ) is a lower bound on the storage at node vat time θ. Note that we

explicitly allow “negative” storage. We assume that the lower bound Lvis zero for

all nodes vwhen talking about the original network. The reason for introducing lower

bounds (Lv)v∈V\{s,t}is to unify the notation later when we introduce the concept of

residual networks. In a residual network Lv(θ) can be nonzero for some node vand

some θ∈R, which indicates the maximum amount of flow that can be reduced from

the available storage at node vat time θ.

We assume that there is no initial storage at any node and flow must not remain

at any node except sand t. This means that the values Yv(−∞) := limθ→−∞ Yv(θ)

and Yv(∞) := limθ→∞ Yv(θ) must be zero for each node v∈V\ {s, t}. Notice that

both limits exist since Yvis of bounded variation. Therefore, for each v∈V\ {s, t},

we require Uv(−∞) = Uv(∞) = Lv(−∞) = Lv(∞) = 0.

A Borel flow xwith corresponding storage Yfulfills the node capacity constraint

at node v∈V\ {s, t}if

−Lv(θ)≤Yv(θ)≤Uv(θ) (2)

for all θ∈R. The Borel flow xis called an s-tBorel flow if it satisfies the node capacity

constraint at all nodes v∈V\ {s, t}. The value val(x) of an s-tBorel flow xis defined

as the total net flow out of node s, that is,

val(x) := X

e∈δ+(s)

|xe| − X

e∈δ−(s)

|xe|.

Here and subsequently, |xe|denotes the total amount of flow entering arc eover time,

i.e., |xe|:= xe(R). Notice that, due to flow conservation, val(x) is equal to the total

net inflow into node t. An s-tBorel flow is called maximum if it has maximum value

among all s-tBorel flows.

The problem which we analyze in this paper is:

Maximum Borel Flow Problem (MBFP)

Input: A network consisting of a directed graph G:= (V, E), a source

s∈V, a sink t∈V, arc capacities ue:B → R≥0for e∈E, and

node capacities Uv:R→R≥0and Lv:R→R≥0for v∈V\ {s, t}.

Task: Find a maximum s-tBorel flow x.

A natural question arising here is whether there exists a maximum s-tBorel flow.

As we see in the next section we are able to prove the existence of such a Borel flow

if ueis finite (i.e., ue(R)<∞) for each arc e∈E. Therefore we assume that ueand,

hence, xeare finite for each arc ethroughout the rest of the paper.

In what follows, we briefly illustrate how MBFP includes the maximum flow over

time problem in both discrete and continuous models as special cases. Since these mod-

els are defined on a time interval [0, T ) we have to set up the arc capacities such that no

flow can be sent along an arc eoutside the interval [0, T ), i.e., ue(R\[0, T )) = 0. If arc

capacities (ue)e∈Eare discrete measures, concentrated on a finite set Ω={θ1,...,θm}

(e.g., Ω={0,1,...,T −1}), then, for each arc e∈E,xemust be a measure concen-

trated on Ω. Here xe({θ}) gives the amount of flow entering arc eat time step θ∈Ω

which is bounded from above by ue({θ}).

We turn now to the continuous model. Let the arc capacities (ue)e∈Ebe abso-

lutely continuous with respect to the Lebesgue measure. It follows from the Radon–

Nikodym Theorem (see, e.g., [5]) that for each arc e∈Ethere exists a Lebesgue

measurable function u′

e: [0, T )→R≥0such that ue(B) = RBu′

edθ for each Borel

set B. Since xe(B)≤ue(B) for each arc e∈Eand each Borel set B, the mea-

sure xeis also absolutely continuous, and hence there exists a Lebesgue measurable

function x′

e: [0, T )→R≥0such that xe(B) = RBx′

edθ for each B. It is well-known

that 0 ≤xe(B)≤ue(B) for each Borel set Bimplies 0 ≤x′

e(θ)≤u′

e(θ) for almost

every θ∈[0, T ). Hence, the value x′

e(θ) can be interpreted as the rate of flow (i.e.,

amount of flow per time unit) entering arc eat the point in time θand the value u′

e(θ)

as an upper bound on the flow rate into arc eat time θ.

3 An Infinite-dimensional Linear Program for MBFP

As mentioned previously, a natural question for MBFP is whether there exists a max-

imum s-tBorel flow. In order to answer this question, we provide a mathematical

formulation of MBFP and prove the existence of an optimal solution for the corre-

sponding problem. For it and throughout this paper, we use the following notation and

we also refer to Appendix A for readers unfamiliar with measure theory. For conve-

nience, we denote the measures by small letters (such as µ,ν,f,y,z,u,h) and their

corresponding distribution functions by capital letters (such as M,N,F,Y,Z,U,H).

Moreover, for a real value τand a Borel measure µthe shifted measure µ−τis defined

by (µ−τ)(B) = µ(B−τ) for each B∈ B, where B−τ:= {θ−τ|θ∈B}. In this

case, the distribution function of µ−τis denoted by M−τ.

Defining the mathematical program, we recall that for each node v∈V\ {s, t},

the storage function Yvis a right continuous function of bounded variation and more-

over Yv(−∞) = 0 (because of (2) and the assumption Lv(−∞) = Uv(−∞) = 0). This

implies that Yvis a distribution function for each v∈V\{s, t}and thus there is a corre-

sponding signed Borel measure yvderived from the formula yv(−∞, θ]=Yv(θ). For

a Borel set B, the value yv(B) can be interpreted as the overall change in storage at v

over the Borel set B. Then the flow conservation constraint (1) at node v∈V\ {s, t}

can be written as

e∈δ+(v)

xe−X

e∈δ−(v)

(xe−τe) + yv= 0 .(3)

Following our above discussion, a mathematical formulation of MBFP is given by

the following infinite-dimensional linear program:

max X

e∈δ+(s)

|xe| − X

e∈δ−(s)

|xe|

s.t. X

e∈δ+(v)

xe−X

e∈δ−(v)

(xe−τe) + yv= 0 ∀v∈V ,

0≤xe≤ue∀e∈E ,

−Lv≤Yv≤Uv∀v∈V\ {s, t},

−Ys≥0,

Yt≥0.

(MBFP)

For every Borel flow x= (xe)e∈Ea signed measure y= (yv)v∈V\{s,t}with correspond-

ing distribution function Y= (Yv)v∈V\{s,t}is uniquely determined by (3). If xand Y

satisfy the constraints of (MBFP), we say that x(with corresponding storage Y) is

feasible. The optimum value of (MBFP) is defined as the supremum of val(x) over all

feasible Borel flows x. The following theorem shows that there exists a feasible Borel

flow which achieves the optimum value of (MBFP) and thus the maximum in (MBFP)

is well defined. Note that we call such an xmaximum Borel flow.

Theorem 1 There exists a maximum Borel flow for the problem (MBFP).

Proof Let Rbe the feasible region of (MBFP), that is, the set of all feasible Borel

flows. The feasible region Ris nonempty since the zero flow is feasible. Moreover, Ris

bounded since by our assumption ueis finite for each e∈Eand hence, for any feasible

Borel flow xwe have

||x|| := X

e∈E

|xe| ≤ X

e∈E

|ue|<∞.(4)

By the Riesz Representation Theorem (see, e.g., [5]), the space M(R) of finite Borel

measures on Ris the topological dual of the space C(R) of continuous functions on R.

We can show by a similar argument as in [16] that Ris closed in the weak topol-

ogy σ(M(R), C(R)). On the other hand, we know by Alaoglu’s Theorem (see again [5])

that the closed unit ball of the space M(R) is compact in the weak topology. Hence, we

can conclude that Ris compact in the weak topology on M(R). This establishes the

result since the objective function of (MBFP) is a linear σ(M(R), C(R))-continuous

functional and hence attains its maximum over a compact set. For a detailed treatment

of the methodology we refer to [1, Chapter 3]. ⊓⊔

4 Borel cuts

In the static framework of network flows, an s-tcut is defined as a subset S⊆Vof

nodes with s∈Sand t∈V\S. The capacity cap(S) := Pe∈δ+(S)ueis defined as

the sum of the capacities of arcs going from the s-side Sto the t-side V\S. It is a

famous result that the value of a maximum s-tflow equals the minimum capacity of

an s-tcut. This is well-known as the MaxFlow-MinCut Theorem which is due to Ford

and Fulkerson [8]. We wish to develop a similar result for Borel flows. The first step is

to extend the definition of an s-tcut and its capacity to the case of Borel flows in an

elaborate way.

We define a Borel cut S:= (Sv)v∈Vby measurable sets Sv, one for each v∈V.

A Borel cut S= (Sv)v∈Vis called an s-tBorel cut if Ss=Rand St=∅. We denote

with Sc

v:= R\Svthe complement of Sv. We say that node vbelongs to the s-side of S

for the points in time θ∈Svand to the t-side of Sfor the points in time θ∈Sc

v. Thus,

an arc e= (v, w) connects the s-side to the t-side for all times in Sv∩(Sw−τe)c.

Since we want to find a tight upper bound on the maximum value of an s-tBorel flow

we are interested in the capacity of an s-tBorel cut. For technical reasons we restrict

the definition of s-tBorel cuts (the reasons are discussed below before Lemma 1). For

this and the remainder of the paper, let M≻0be the set of all points θ∈Rwhere a

distribution function Mor its left limit is positive at θ. More precisely:

M≻0:= θ∈R|M(θ−)>0 or M(θ)>0,(5)

where Mv(θ−) denotes the limit of Mvat θfrom left, i.e., Mv(θ−) := limϑրθMv(ϑ).

Since Mis right continuous the set M≻0is the countable union of pairwise disjoint

intervals. Now an s-tBorel cut S= (Sv)v∈Vhas to satisfy the following additional

property: For every node v∈V\ {s, t}the set

Γv:= Sv∩U≻0

v(6)

is a countable union of pairwise disjoint intervals.

Let S= (Sv)v∈Vbe an s-tBorel cut and consider a node v. By definition, Γvis

expressible as Si∈JvIv,i, where Jvis a countable set of indices and Iv,i,i∈Jv, are

pairwise disjoint intervals. Each interval Iv,i is supposed to be inclusion-wise maximal,

i.e., there is no interval I⊆Γvstrictly containing Iv,i. We keep this assumption

throughout the paper; whenever we express Γvas a countable union of intervals we

suppose that the intervals are inclusion-wise maximal. Let αv,i and βv,i be the left

and right boundary of the interval Iv,i, respectively. An interval Iv,i can be of the

form (αv,i, βv,i), [αv,i, βv,i), (αv,i, βv,i], or [αv,i, βv,i]. Therefore we partition the set Jv

of indices into four subsets. Let J1

v(J2

v,J3

v, and J4

v) be the set of indices ifor which Iv,i

is open (left-closed & right-open, right-closed & left-open, and closed, respectively).

With these constructions, the capacity cap(S) of Sis defined by

cap(S) := X

e=(v,w)∈E

ueSv∩(Sw−τe)c+

v∈V\{s,t}X

i∈J1

v∪J2

Uv(βv,i−) + X

i∈J3

v∪J4

Uv(βv,i).

(7)

We set the capacity cap(S) to ∞if any infinite sum does not converge. The first sum

indicates the contribution of capacities of arcs at the points in time when the arcs cross

the cut; the second one represents the contribution of the storage capacities at points

in time when node vpasses the cut from the s-side to the t-side. Note that points in

time at which the capacity is zero do not contribute any value to the capacity of the

cut. Therefore it is sufficient to consider only Γvwhen considering the contribution of

node capacities to the capacity of the cut. We refer to an s-tBorel cut whose capacity

is minimum among all s-tBorel cuts as a a minimum Borel cut.

In the following we shortly explain why we restrict the definition of an s-tBorel

cut Sto those cuts such that the each set Γv=Sv∩U≻0,v∈Vis the countable union

of pairwise disjoint intervals. First notice that, in general, Svcan be any measurable

set (e.g., the set of irrational numbers, the Cantor set and so on). If we do not consider

the restriction on the sets Γv, then the contribution of node capacities to the capacity

of Sbecomes unclear. In particular, there is no obvious definition of the points in

time at which a node vpasses the cut from the s-side to the t-side. For overcoming

this problem one could require that Sv, instead of the set Γv, is a countable union of

intervals for each node v∈V. But as we observe below in Example 1, there might be

no s-tBorel cut whose capacity equals the value of a maximum Borel flow. On the

other hand, we will show that there always exists a minimum Borel cut Sin which the

sets Γv,v∈V, are countable union of intervals. First we prove that the capacity of

an s-tBorel cut is an upper bound on the value of any s-tBorel flow. For the proof, we

require the following technical result, the proof of which can be found in Appendix B.

Lemma 1 Let µbe a finite signed Borel measure on Rwith a nonnegative distribution

function M. Let A:= R\M≻0be the set of points θ∈Rfor which Mis continuous

and zero at θ. Then µ|A= 0, i.e., the set Ais a strict µ-null set.

Lemma 2 The capacity of any s-tBorel cut is an upper bound on the value of any

s-tBorel flow.

Proof Let xbe an s-tBorel flow with corresponding storage yand let Sbe an s-tBorel

cut. Since Ss=Rand R−τ=Rfor each τ∈R, we can express the value of xas

val(x) = X

e∈δ+(s)

xe(Ss)−X

e∈δ−(s)

(xe−τe)(Ss).(8)

Moreover, as St=∅, we have

e∈δ+(t)

xe(St)−X

e∈δ−(t)

(xe−τe)(St) = 0 .(9)

On the other hand, the flow conservation constraint at node v∈Vis separately valid

for all B∈ B and hence for its corresponding set Sv. By summing up these equations

over v∈V\ {s, t}, we get

v∈V\{s,t}

X

e∈δ+(v)

xe(Sv)−X

e∈δ−(v)

(xe−τe)(Sv)

+X

v∈V\{s,t}

yv(Sv) = 0 .(10)

Thus, adding (8), (9), and (10) leads to

val(x) = X

v∈V

X

e∈δ+(v)

xe(Sv)−X

e∈δ−(v)

(xe−τe)(Sv)

+X

v∈V\{s,t}

yv(Sv).(11)

In the first term on the right hand side of the above equation, each arc appears ex-

actly once with a positive sign and exactly once with a negative sign. Therefore the

first term is equal to sum of xe(Sv)−(xe−τe)(Sw) over all arcs e= (v, w)∈E.

Since (xe−τe)(Sw) = xe(Sw−τe) for each arc e= (v, w)∈E, a single term of this

sum is bounded by ueSv∩(Sw−τe)cas follows:

xe(Sv)−xe(Sw−τe) = xeSv∩(Sw−τe)c−xeSc

v∩(Sw−τe)

≤ueSv∩(Sw−τe)c.

Hence, the first term is bounded by X

e=(v,w)∈E

ueSv∩(Sw−τe)c.

It remains to bound the second term on the right hand side of (11). Since Yv≤Uv

we have Y≻0

v⊆U≻0

vand thus Sv\U≻0

v⊆R\U≻0

v⊆R\Y≻0

v. On the other hand,

Lemma 1 shows that R\Y≻0

vis a strict yv-null set. So we get yv(Sv\U≻0

v) = 0 and as

a consequence yv(Sv) = yv(Sv∩U≻0

v) = yv(Γv). Hence, we can bound a single term

of the sum in the second term of (11) as follows:

yv(Sv) = yv(Γv) =

∞

i=1

yv(Iv,i)

i∈J1

vYv(βv,i−)−Yv(αv,i)+X

i∈J2

vYv(βv,i−)−Yv(αv,i−)

i∈J3

vYv(βv,i)−Yv(αv,i)+X

i∈J4

vYv(βv,i)−Yv(αv,i−)

≤X

i∈J1

v∪J2

Uv(βv,i−) + X

i∈J3

v∪J4

Uv(βv,i).

Hence, the second term is bounded by X

v∈V\{s,t}

X

i∈J1

v∪J2

Uv(βv,i−)+ X

i∈J3

v∪J4

Uv(βv,i).

This concludes the proof. ⊓⊔

5 Residual networks

As already mentioned before, we wish to develop a MaxFlow-MinCut Theorem for our

setting of flows over time, that is, the existence of an s-tBorel flow xand an s-tBorel

cut Sfor which val(x) = cap(S) holds. Once this is proved, we can conclude that x

is a maximum Borel flow and Sis a minimum Borel cut because of Lemma 2. The

existence of a maximum s-tBorel flow is guaranteed by Theorem 1. Thus, to derive

a MaxFlow-MinCut theorem, it suffices to construct an s-tBorel cut whose capacity

equals the value of a maximum s-tBorel flow. One approach is to go along the same

lines as in the static case. More precisely, starting from a given maximum s-tBorel

flow x, we try to come up with an s-tBorel cut whose capacity equals the value of x.

Thus, we need the concept of residual networks as well as augmentation for Borel flows.

For an arc e= (v, w)∈Ewe denote the corresponding backward arc (w, v)

by ←−

e:= (w, v). If for some nodes v, w ∈Vboth arcs (v, w) and (w, v) belong to Ewe

have to introduce backward arcs for each of them leading to an inconsistence notation.

This conflict could be resolved by introducing an artificial node on one of the arc. So

we assume without loss of generality that this problem never occur. The transit time

of a backward arc ←−

ewith e∈Eis defined by τ←−

e:= −τe. Notice that the transit time

of a backward arc is in general negative. We denote the set of all backward arcs by ←−

and set Er:= E∪←−

With respect to a given Borel flow x, we introduce the following definitions. For

each arc e∈Ewe define the residual capacity of eand the corresponding backward

arc ←−

eas ur

e:= ue−xeand ur

←−

e:= xe−τe, respectively. For each B∈ B,ur

e(B)

and ur

←−

e(B) represent the maximum amount by which flow can be increased and re-

duced, respectively, on arc eover Bwithout violating the constraints 0 ≤xe≤ue.

Let Ybe the storage function induced by x. For each node v∈V\ {s, t}, we

define the upper and lower residual capacity of vas Ur

v:= Uv−Yvand Lr

v:= Lv+Yv,

respectively. For any point in time θ∈R,Ur

v(θ) gives the maximum additional amount

of flow that can be stored at node vat time θand Lr

v(θ) represents the maximum

amount of flow that can be reduced from the available storage at node vat time θ

without violating the constraints −Lv≤Yv≤Uv.

The network consisting of the residual graph Gr:= (V, Er) and the residual ca-

pacities (ur

e)e∈Er, (Ur

v)v∈V, and (Lr

v)v∈Vis called the residual network of Gwith

respect to the Borel flow x. An s-tBorel flow fin Grwith val(f)>0 is called an

augmenting s-tBorel flow.

Lemma 3 Let xbe an s-tBorel flow in G. If there is an augmenting s-tBorel flow f,

then xis not maximum.

Proof We define the augmented Borel flow xfby

e:= xe+fe−(f←−

e−τ←−

e) for all e∈E.

We prove that xfis a feasible Borel flow of value val(xf) = val(x) + val(f).

First we show that 0 ≤xf

e≤uefor all arcs e∈E. Because of the definition of

residual capacities, for each arc e∈Ewe get

e=xe+fe−(f←−

e−τ←−

e)≤xe+fe≤xe+ (ue−xe) = ueand

e=xe+fe−(f←−

e−τ←−

e)≥xe−(f←−

e−τ←−

e)≥xe−(xe−τe) + τe= 0 .

Let zand yfbe the storage induced by fand xf, respectively, in the residual

network Grand the original network G. For all v∈V1 we show that yf

v=yv+zv

in the following. Note that xand fsatisfy (MBFP) on Gand Gr, respectively, and

that Gis a subgraph of Gr. By definition of storage yfwe get

v=X

e∈δ−(v)

(xf

e−τe)−X

e∈δ+(v)

e∈δ−(v)xe+fe−(f←−

e−τ←−

e)−τe−X

e∈δ+(v)xe+fe−(f←−

e−τ←−

e).

Further, we know that −(f←−

e+τe)−τeis equal to −f←−

eand not equal to −f←−

e−2τe

since the subtraction of a real number is a (horizontal) shifting of the measure. Thus,

expanding the shifting in the first sum leads to

v=yv+X

e∈δ−(v)

(fe−τe) + X

e∈δ+(v)

(f←−

e−τ←−

e)−X

e∈δ+(v)

fe−X

e∈δ−(v)

f←−

If an arc eis contained in δ+(v) and δ−(v), then the backward arc ←−

eis contained

in δ−

Gr(v) and δ+

Gr(v), respectively. Hence, we obtain

v=yv+X

e∈δ−

Gr(v)

(fe−τe)−X

e∈δ+

Gr(v)

fe=yv+zv.

For the feasibility, it remains to show −Lv≤Yf

v≤Uvand |yf

v|= 0 for all v∈V\{s, t}.

This is obtained as follows:

v=Yv+Zv≥Yv−(Lv+Yv) = −Lv,

v=Yv+Zv≤Yv+ (Uv−Yv) = Uv,

|yf

v|=|yv+zv|=|yv|+|zv|= 0 .

Thus xfis a feasible Borel flow. In particular, this means that xf

eis nonnegative for

each arc e∈E. Further, shifting does not influence the norm of a measure. Therefore

we get for the flow value of xf:

val(xf) = X

e∈δ+(s)

|xf

e| − X

e∈δ−(v)

|xf

e∈δ+(s)xe+fe−(f←−

e−τ←−

e)−X

e∈δ−(s)xe+fe−(f←−

e−τ←−

e)

e∈δ+(s)|xe|+|fe| − |f←−

e|−X

e∈δ−(s)|xe|+|fe| − |f←−

e|

= val(x) + X

e∈δ+

Gr(s)

fe−X

e∈δ−

Gr(s)

= val(x) + val(f).

This completes the proof since xfis a feasible Borel flow with a strictly larger flow

value than x.⊓⊔

s v t

λ ud

Fig. 1 Network for Example 1. The capacities are shown on the arcs and all transit times

are 0.

6 Reachability

The next step is to find a Borel cut whose capacity is equal to the value of a maximum

Borel flow. As already mentioned, it is quite natural to carry over the classical static

approach. In the static case, a minimum cut can be defined by the nodes that are

reachable from source sin the residual network of a maximum flow. For the case of

Borel flows this means that a minimum Borel cut can be defined by the times when a

node is reachable from s. It turns out, however, that Borel flows require a somewhat

more intricate definition, as the following three examples indicate. Example 1 shows

that we must exclude certain points in time and Example 2 shows that we also must

add certain points in time. Moreover, Example 3 shows that a careful treatment is

required in adding or excluding certain points in time.

Example 1 Consider the network depicted in Figure 1 which consists of three nodes s,v,

and tand of two arcs e1= (s, v) and e2= (v, t). All transit times are 0. The capacity

of arc e1is set to the Lebesgue measure λ(i.e., λ([a, b]) = b−afor all real a≤b)

and the capacity of arc e2is set to some discrete measure udconcentrated on the

rational numbers (i.e., supp(ud) = Q). Further, storage of flow is not permitted at the

intermediate node v, i.e., Uv=Lv= 0. Hence, all flow arriving at vmust immediately

enter arc e2. Thus, no measurable amount of flow can be routed from sto t, i.e., the

zero flow is a maximum Borel flow. Therefore the original network and the residual

network coincide.

Let us consider the points in time at which node vis reachable as one would expect

these points to appear in a minimum Borel cut. It is obvious that flow is able to reach

node vat every point in time θ∈Rsince the capacity of e1is equal to the Lebesgue

measure. So we would expect the cut Sdefined by Ss:= R,Sv:= R, and St:= ∅to

be a minimum s-tBorel cut. But we have cap(S) = ud(R) which is far away from the

maximum Borel flow value 0. Actually, setting Sv:= Rmeans that flow can enter arc e2

at points in time θ∈supp(ud) since the support of udis trivially contained in Sv. But

this is not really true since no flow can enter arc e2at any point in time. We therefore

exclude the support of udand set Sv:= R\supp(ud) = R\Q, which leads to a minimum

Borel cut of capacity 0. Note that supp(ud) is a λ-null set, i.e., λ(supp(ud)) = 0. Hence,

the exclusion of supp(ud) has no impact on the flow behavior on arc e1.

Example 1 shows also that continuous and discrete flows can be mixed only if there

is some storage capacity that allows to convert one quantity into the other. Also note

that every Borel cut Swhere Svis a countable union of intervals has a capacity strictly

greater than zero. More precisely, we have cap(S) = λ(Sc

v)+ud(Sv); if Svis a countable

union of intervals that does not contain any rational point, then it excludes a subset

of Rwith nonzero Lebesgue measure (i.e., λ(Sc

v)>0), and if Svcontains some rational

points, then ud(Sv)>0. Hence, the restriction that Γv(in Example 1 Γv=∅) is the

countable union of intervals is not extendable to the whole set Sv.

Example 2 Consider the network depicted in Figure 2(a) with three nodes s,v, and t

and two arcs e1= (s, v) and e2= (v, t). On arc e1we can route two units of flow at

s v t

ue1ue2

(a) Original network.

time

(b) Time expanded network.

Fig. 2 Network for Example 1. The capacities are shown on the arcs and all transit times

are 0.

time 0 and arc e2allows routing one unit of flow at time 1. Further, storage of two

flow units is allowed at the intermediate node vwithin the time interval [0,1). The

corresponding time expanded network is shown in Figure 2(b). In particular, we have

ue1(B) = (2 for 0 ∈B

0 for 0 /∈Band ue2(B) = (1 for 1 ∈B

0 for 1 /∈Bfor all B∈ B ,

Uv(θ) = (2 for θ∈[0,1)

0 for θ /∈[0,1) and Lv(θ) = 0 for all θ∈R.

In this example, a maximum Borel flow routes one unit of flow from sto tas follows:

One unit of flow enters arc e1at time 0 and arrives at vat time 0. After waiting at v

within the time interval [0,1), the flow unit enters arc e2at time 1 and reaches tat

the same time. Let xbe this Borel flow. Then xis given as follows:

xe1(B) = (1 for 0 ∈B

0 for 0 /∈Band xe2(B) = (1 for 1 ∈B

0 for 1 /∈Bfor all B∈ B , (12)

with storage function Yv(θ) = (1 for θ∈[0,1)

0 for θ /∈[0,1) .(13)

Thus the signed measure yvis discrete, concentrated on the set {0,1}with yv({0}) = 1

and yv({1}) = −1.

Now consider the residual network Grwith respect to x. It is not hard to see that

flow is able to reach node vat every point in the time interval [0,1) since an additional

flow unit can reach node vat time 0 and then wait at node vwithin this time interval.

Therefore we would expect that the cut Sdefined by Ss:= R,Sv:= [0,1), and St:= ∅

is a minimum s-tBorel cut. Let us compute the capacity of S. The arc capacities have

no contribution to cap(S) (i.e., the first sum in (7) is zero) and the node capacity Uv

contributes a value of 2 to cap(S) since Γv= [0,1) and Uv(−1) = 2. Thus cap(S) = 2,

which is not equal to the value of x. We now observe that Ur

v(1−)>0 and flow

can reach node vwithin the interval [0,1). In fact, we have Ur,≻0

v= [0,1]. It is thus

reasonable to consider the point 1 as an element of Svand define a new s-tBorel cut S′

by S′

v:= Sv∪ {1}= [0,1]. Recall that right-open and right-closed intervals are treated

differently in computing the capacity of an s-tBorel cut. Here we have cap(S′) = 1

and get a minimum Borel cut of capacity 1.

Example 3 Consider Example 2 but with the node capacity Uvgiven as:

Uv(θ) = (1−θfor θ∈[0,1)

1 for θ /∈[0,1) for all θ∈R.

Here one unit of flow can reach node vat time 0. This flow has to wait at node v

until time 1, before routing towards the sink. On the other hand, the node capacity

at vdecreases to zero when the time tends to 1. Therefore, intuitively, no flow can be

sent from sto t. Hence, the maximum Borel s-tflow is zero and, consequently, the

original network and the residual network coincide.

We are now interested in computing a Borel cut of capacity zero. We have U≻0

v=R

and flow is able to reach node vat time 0. So a natural candidate Sfor a minimum

Borel s-tcut can be given by Ss:= R,Sv:= [0,∞), and St:= ∅. The arc capacity ue1

has no contribution to cap(S), the arc capacity ue2has a contribution of value 1

to cap(S), and the node capacity Uvcontributes a value of 1 to cap(S) since Γv= [0,∞)

and Uv(∞) = 1. Thus we have cap(S) = 2 which is far away from the maximum Borel

flow value 0. On the other hand, although U≻0

v=R, flow can not reach node vwithin

the interval [1,∞) as Uv(1−) = 0. Hence, it is reasonable to restrict Svto the time

interval [0,1), which leads to a Borel cut of capacity 0. It is also worth to mention that

despite the similarities to Example 2, the point in time 1 must be excluded from Svin

this example.

In Example 3, the minimum Borel cut is obtained by setting Sv:= [0,1) as flow

can reach node vat time 0 and [0,1) ⊂U≻0

v. However, although U≻0

v=R, no point

in [1,∞) is reachable as Ur

v(1−) = 0. In fact, U≻0

vis the union of the intervals (−∞,1)

and [1,∞) where for all a, b in one of these two intervals with a < b there exists

an ǫ > 0 such that U≻0

v|[a,b)> ǫ. Intuitively, this ensures that some flow arriving at v

at time acan be stored in vuntil time b. This motivates the following concept of

positive intervals.

Let µbe a Borel measure with corresponding distribution function M. Recall

that M≻0, defined by (5), denotes the set of all points in time where Mor its left

limit is positive at θ. Further, we call an interval Ipositive if for all a, b ∈Iwith a < b

there exists an ǫ > 0 such that M|[a,b)> ǫ. The following lemma shows that M≻0is

expressable as a countable union of such intervals, the proof of which can be found in

Appendix B. Note that, as already mentioned, M≻0is the countable union of pairwise

disjoint intervals. Hence, each interval out of a countable union can be assumed to be

positive. Further, defining the capacity of a Borel cut via the countable union of inclu-

sionwise maximal intervals as in (7) leads to the same value as considering inclusionwise

maximal positive intervals instead.

Lemma 4 Let Mbe a distribution function. Then the set M≻0can be written as a

countable union of pairwise disjoint positive intervals.

At this point, let us introduce some more notations which are used in the the rest

of the paper. We define M>0and M<|µ|to denote the set of all points θ∈Rsuch

that M(θ)>0 and M(θ−)<|µ|, respectively. More precisely,

M>0:= θ∈R|M(θ)>0and M<|µ|:= θ∈R|M(θ−)<|µ|.

Notice that these two sets are intervals.

In the following we construct a procedure for deriving the points in time when a

node is reachable from s. The procedure gets as input any network and produces as

output sets Si

vfor each i∈Nand each node v∈V\ {s, t}. A set Si

vcontains all points

in time at which flow is able to arrive at node vusing exactly iarcs. These sets are

computed inductively over i. In order to compute Si

vfor a fixed vand a fixed i, we

first consider the sets Si−1

wof times at which flow is able to arrive at any predecessor

node wof v(i.e., (w, v)∈E) along exactly i−1 arcs. From these times we derive the

points in time at which vis reachable using exactly iarcs (including arc (w, v) as the

last arc) and waiting occurs at v. It follows from Example 2 that we must add certain

points in time for the latter case. We next consider the case where no waiting is allowed

at vand obtain the set Si

v. Example 1 shows us that we must exclude certain points

in time. A Borel cut S:= (Sv)v∈Vis then given by Sv:= Si∈NSi

vfor v∈V.

Reachability Procedure

Input: A network consisting of a directed graph G, transit times τe, arc

capacities ue, and node capacities Uvand Lv.

Output: Sets Si

vfor v∈Vand i∈Ndetermining at which times a node is

reachable from susing exactly iarcs.

(1) Initialize i:= 0 and Sj

v:= (Rif v=sand j= 0

∅otherwise for v∈Vand j∈N.

(2) For each arc e∈E, let ge:= ue|Si

vwhere v= tail(e).

(3) For each node v∈Vdo:

(a) Define µ1:= X

e∈δ−(v)

(ge−τe) and µ2:= X

e∈δ+(v)

ue.

(b) Let U≻0

v=[

k∈J

Ikbe the disjoint union of positive intervals where J⊆N.

Set hk:= µ1|Ikfor each k∈J.

Set S+:= [

k∈JH>0

k∩Ik.

v=[

k∈J

Ikbe the disjoint union of positive intervals where J⊆N.

Set hk:= µ1|Ikfor each k∈J.

Set S−:= [

k∈JH<|hk|

k∩Ik.

(d) Use the Lebesgue Decomposition Theorem in order to find νac and νssuch

that:

–µ2=νac +νs,

–νac is absolutely continuous with respect to µ1,

–νsand µ1are mutually singular.

Find a set A⊆Rsuch that µ1(A) = 0 and νs(Ac) = 0.

Set ¯

A:= A∪(U≻0

v\S+)∪(L≻0

v\S−).

Set S0:= supp(µ1)\¯

(e) Set Si+1

v:= S0∪S+∪S−.

(4) Set i:= i+ 1 and go to (2).

As mentioned already, the positive intervals in Steps (3b) and (3c) are supposed

to be inclusion-wise maximal. It is also worth to mention that for each v∈V, the

sequence Si

vof sets is not necessarily monotonic with respect to inclusion. Further,

note that in general, the Reachability Procedure never terminates and even re-

quires infinite memory. But this causes no problem in theory since the Reachability

Procedure is not meant as an algorithm but rather as a definition of the sets Si

From these sets we deduce a Borel cut S:= (Sv)v∈Vby Sv:= Si∈NSi

vfor v∈V.

time

(a) Forward arcs and upper storage

bounds.

-1

time

(b) Backward arcs and lower storage

bounds.

Fig. 3 Residual network for Example 5. The capacities are shown and all transit times are 0.

Hence, Scan be seen as an output of the procedure. Nevertheless, it is of great interest,

whether the Reachability Procedure terminates in finite time or not. We discuss

briefly some arising questions in the conclusion. We next illustrate the Reachability

Procedure using the instances of Example 1 and 2.

Example 4 Consider the instance of Example 1. Since the zero flow is a maximal Borel

flow the sink tshould not be reachable. Since the source shas no incoming arc the

sets Si

sare never changed after initialization, i.e, we have S0

s=Rand Si

s=∅for i≥1.

When processing the intermediate node vin the first iteration, we obtain µ1=λ

and µ2=ud. As λand udare mutually singular, we have νac = 0 and νs=ud.

Since λ(supp(ud)) = 0 and ud(R\supp(ud)) = 0 we set A:= supp(ud). Hence, this

implies S0= supp(λ)\supp(ud) = R\supp(ud). Since the storage of flow at node v

is not permitted, we have U≻0

v=L≻0

v=∅, which implies S+=S−=∅as well. This

leads to S1

v=R\supp(ud). In each of the following iterations i≥1, we have Si

v=∅

since µ1=λ|Si

s=λ|∅=∅, and as a result Sv=R\supp(ud).

Next we consider sink t. In each iteration, we have µ1=µ2= 0, which leads

to St=∅. Hence, the Borel cut constructed by the Reachability Procedure equals

Ss=R,Sv=R\supp(ud) and St=∅, which has a capacity of zero.

Example 5 In this example, we consider Example 2 and the residual network with

respect to the Borel flow xgiven by (12). Let νbe the measure concentrated on {0}

with ν({0}) = 1 and C:R→Rbe the function defined by C|[0,1) = 1 and C|R\[0,1) = 0.

Then the residual arc and node capacities are given as follow (see also Figure 3):

e1=ur

←−

e1=ν , ur

e2= 0 , ur

←−

e2=ν−1,and Ur

v=Lr

v=C .

We consider the process of the procedure in the first iteration. For node vwe have

µ1=ur

e1|S0

s+ur

←−

e2|S0

t=νand µ2=ur

e2+ur

←−

e1=ν .

In Step (3b), as Ur

v≻0= [0,1], we get h1=µ1|[0,1] =ν. Thus, we have H>0

1= [0,∞)

and consequently S+=H>0

1∩[0,1] = [0,1]. In Step (3c), we have Lr

v≻0= [0,1]

and h1=νas in Step (3b). Since H<|h1|

1= (−∞,0] we get S−=H<|h1|

1∩[0,1] = {0}.

Since it holds that µ2=µ1, we have νac =µ2,νs= 0, and set A:= ∅. This gives

us ¯

A= (−∞,0) and consequently S0= supp(ur

e1) = {0}. By the union of S0,S+

and S−, we obtain S1

v= [0,1]. For node t, we have µ1=ur

e2|S0

v= 0 implying S1

t=∅.

In the second iteration, we observe for node vthat µ1=ur

e1|S1

s+ur

←−

e2|S1

t= 0.

Thus, we get S2

v=∅. For node t, we have µ1=ur

e2|S1

v= 0 implying again S2

t=∅. In

the third iteration, we get again S3

v=∅and S3

t=∅.

v w

fefe′

Fig. 4 The setting of Lemma 6.

We terminate the procedure after the third iteration since Svand Stremain the

same. Summarizing, we get the Borel cut Ss=R,Sv= [0,1] and St=∅, whose

capacity is 1.

In the remainder of this section we show that if tis reachable in the residual

network, i.e., Si∈NSi

t6=∅, then the corresponding Borel flow is not maximal. The

proof will be carried out via a sequence of lemmas. The first one states that excluding

the set ¯

Afrom supp(µ1) in Step (3d) does not change the measure µ1, i.e., µ1|¯

A= 0.

This result will be used later.

Lemma 5 In each iteration of the procedure, ¯

Ais a strict µ1-null set, that is, µ1|¯

A= 0.

Proof Recall that ¯

Ais defined as ¯

A:= A∪(U≻0

v\S+)∪(L≻0

v\S−). From the con-

struction of Awe know that µ1(A) = 0. Since µ1is nonnegative, we get µ1|A= 0.

Thus it is sufficient to prove that both U≻0

v\S+and L≻0

v\S−are µ1-null sets.

In order to prove that U≻0

v\S+is a µ1-null set, first observe that U≻0

v=Sk∈JIk

is the countable union of pairwise disjoint positive intervals where J⊆N. Hence, it is

enough to show that Ik\S+is a µ1-null set for each k∈J. Fix a k∈J. Because of the

definition of S+in Step (3b) we have Ik\S+=Ik\H>0

k∩Ik=Ik∩(H>0

k)cwhere Hk

is the distribution function of the (nonnegative) measure hk:= µ1|Ik. Further we have

µ1(Ik∩(H>0

k)c) = hk(H>0

k)c. The definition of H>0

kimplies hk((−∞, θ]) = 0 for

each θ∈(H>0

k)c. Since (H>0

k)c=Sθ /∈H>0

k(−∞, θ] holds, we have hk(H>0

k)c= 0

proving µ1(Ik\S+) = 0.

It remains to show that L≻0

v\S−is a µ1-null set. Let L≻0

v=Sk∈JIkbe the

countable union of pairwise disjoint positive intervals where J⊆N. Hence, it is suffi-

cient to show that Ik\S−is a µ1-null set for each k∈J. Fix a k∈J. It follows from

the definition of S−in Step (3c) that Ik\S−=Ik\H<|hk|

k∩Ik=Ik∩(H<|hk|

k)c

where Hkis the distribution function of the (nonnegative) measure hk:= µ1|Ik.

Further we have µ1(Ik∩(H<|hk|

k)c) = hk(H<|hk|

k)c. Moreover, from the definition

of H<|hk|

k, we get hk([θ, ∞)) = |hk| − Hk(θ−) = 0 for each θ∈(H<|hk|

k)c. This implies

hk(H<|hk|

k)c= 0 since (H<|hk|

k)c=Sθ /∈H<|hk|

[θ, ∞) holds. Hence, µ1(Ik\S+) = 0.

⊓⊔

Roughly speaking, the next lemma deals with the following situation. Suppose we

are able to route flow out of a certain node wwith departure times in Si

wfor some i.

Then some of this flow can be obtained by routing flow from a predecessor node vwith

departure times in Si−1

valong arc (v, w) and then out of w. In the proof we have to

resolve, among other things, the conflicts established in Examples 1 and 2. We refer to

Figure 4 where the scenario of Lemma 6 is depicted.

Lemma 6 Let w∈V\ {s}be a node and fbe a nonzero measure with f≤ue′|Sn

wfor

some arc e′∈δ+(w)and some n∈N. Then there exists an arc e= (v, w)and nonzero

measures feand fe′such that

|fe|=|fe′|, fe≤ue|Sn−1

v, fe′≤f, and −Lw≤(Fe−τe)−Fe′≤Uw.

Proof Consider the state of the procedure where iis equal to n−1 and node wis

processed in the loop of Step (3). Here, Sn

wis computed and we have (using the notation

of the procedure)

w=S0∪S+∪S−.

Since fis a nonzero measure we obtain 0 < f(R) = f(R\Sn

w) + f(Sn

w). On the other

hand f≤ue′|Sn

wimplies f(R\Sn

w) = 0 because ue′|Sn

w(R\Sn

w) = ue′(∅) = 0. Hence,

it holds that 0 < f(Sn

w)≤f(S0) + f(S+) + f(S−). Therefore, at least one measure

of f|S0,f|S+, and f|S−is nonzero. Consequently, we use the following case distinction:

Case 1: We first consider the case that f|S0is nonzero. Using the notation of the

procedure, we observe that µ2|S0is absolutely continuous with respect to µ1. To see

this, let Bbe a Borel set for which µ1(B) = 0. We write

µ2|S0(B) = νac(S0∩B) + νssupp(µ1)∩B∩¯

Ac.

The first summand on the right hand side is 0 because νac is absolutely continuous

with respect to µ1and we have µ1(B) = 0. Further, the second summand is zero

because 0 ≤νs(¯

Ac)≤νs(Ac) = 0 as A⊆¯

A. Hence, µ2|S0is absolutely continu-

ous with respect to µ1. This implies that f|S0is absolutely continuous with respect

to µ1because f≤µ2(to see this, observe f≤ue′|Sn

w≤ue′≤Pe∈δ+(w)ue=µ2).

Therefore min{µ1, f|S0}is a nonzero measure (see Appendix A for a discussion on the

minimum of two measures). Hence, there exists a Borel set B∈ B such that

0<min{µ1(B), f|S0(B)}= min{X

e=(v,w)∈δ−(w)

(ue|Sn−1

v−τe)(B), f|S0(B)}

≤X

e=(v,w)∈δ−(w)

min{(ue|Sn−1

v−τe)(B), f|S0(B)}

This ensures the existence of an arc e= (v, w) such that f′:= min{(ue|Sn−1

v−τe), f|S0}

is a nonzero measure. Hence, setting fe:= f′+τeand fe′:= f′leads to the desired

result.

Case 2: We next consider the case that f|S+is nonzero. From Step (3b) of the proce-

dure we know that

S+=[

k∈JH>0

k∩Ik

for some J⊆N. Hence, there exists some k∈Jsuch that frestricted to I:= H>0

k∩Ik

is a nonzero measure. Note that Iis an interval and let aIand bIbe the left and the

right boundary of I, respectively. Further, we can exclude the case f|Iis concentrated

on {aI}since this case is already resolved in Case 1. This can be seen as follows: Having

in mind the definitions of restricted and concentrated measures we know that Iis left

closed. Hence, Step (3b) shows µ1({aI})>0. This implies aI∈S0because of Lemma 5

and thus, Case 1 is applicable since f({aI})>0.

In the following we show that there exists a, b, c ∈Iwith a < b < c such that µ1|[a,b]

and f|[b,c]are nonzero measures and Uw|[a,c)≥ǫfor some ǫ > 0. Informally, this

ensures that, without violating the node capacity at w, we can send a small amount of

flow into node wover the time interval [a, b] which leaves vover the time interval [b, c].

Note that f|Iis not concentrated on {aI}due to our assumption. Assuming also

that f|Iis not concentrated on {bI}there exist b, c ∈(aI, bI) with b < c such that f|[b,c]

is a nonzero measure. If f|Iis concentrated on bIwe have bI∈I. Moreover, for c=bI

and any b∈(aI, bI) it holds that f|[b,c]is a nonzero measure. Further, the definition

of Ishows that µ1|[aI,b]is a nonzero measure such that its distribution function is

strictly positive on (aI, b). Thus, there exists an a∈[aI, b)∩Isuch that µ1|[a,b]is a

nonzero measure. Note that if µ1|Iis concentrated on {aI}, then Iis left closed and

we must set a:= aI∈I(otherwise ais taken out of (aI, b]⊂I). Finally, since Iis a

positive interval with respect to Uvthere exists an ǫ > 0 such that Uv|[a,c)≥ǫ.

Because of the definition of µ1, there exists an arc e= (v, w)∈δ−(w) such that the

measure ¯

fe:= ue|Sn−1

v−τerestricted to [a, b] is a nonzero measure. We let

α:= minn¯

fe|[a,b],f|[b,c], ǫo

and define feand fe′as follows:

fe:= α

¯

fe|[a,b]

fe|[a,b]+τeand fe′:= α

f|[b,c]

f|[b,c].

This yields the desired result.

Case 3: It remains to consider the case that f|S−is nonzero which is similar to the

previous case. Recall from Step (3c) that

S−:= [

k∈JH<|hk|

k∩Ik

for some J⊆N. Hence, there is some k∈Jsuch that frestricted to I:= H<|hk|

k∩Ik

is a nonzero measure. Note that Iis an interval and let aIand bIbe the left and the

right boundary of I, respectively. Further, we can assume without loss of generality

that f|Iis not concentrated on {bI}. Otherwise this case is resolved in Case 1 which can

be seen as follows: Because of the definitions of restricted and concentrated measures

we know that Iis right closed in this case. Hence, Step (3c) shows µ1({bI})>0 (Note

that H<|hk|

kis defined via limits from left). This implies bI∈S0because of Lemma 5

and thus, Case 1 is applicable since f({bI})>0.

In the following we show that there exists a, b, c ∈Iwith a < b < c such that µ1|[b,c]

and f|[a,b]are nonzero measures and Lw|[a,c)≥ǫfor some ǫ > 0. Informally, this

ensures that, without violating the node capacity at w, we can send a small amount of

flow into node wover the time interval [b, c] which leaves vover the time interval [a, b].

That is, we route a small portion of flow back in time.

Note that f|Iis not concentrated on {bI}due to our assumption. Assuming also

that f|Iis not concentrated on {aI}there exist a, b ∈(aI, bI) with a < b such

that f|[a,b]is a nonzero measure. If f|Iis concentrated on aIwe have aI∈I. More-

over, for a=aIand any b∈(aI, bI) it holds that f|[a,b]is a nonzero measure. Further,

the definition of Ishows that µ1|[b,bI]is a nonzero measure such that its distribution

function is strictly less than |hk|on (b, bI). Thus, there exists an c∈(b, bI]∩Isuch

that µ1|[b,c]is a nonzero measure. Note that if µ1|Iis concentrated on {bI}, then I

is right closed and we must set c:= bI∈I(otherwise cis taken out of [b, bI)⊂I).

Finally, since Iis a positive interval with respect to Lvthere exists an ǫ > 0 such

that Lv|[a,c)≥ǫ.

Because of the definition of µ1, there exists an arc e= (v, w)∈δ−(w) such that the

measure ¯

fe:= ue|Sn−1

v−τerestricted to [b, c] is a nonzero measure. We let

α:= minn¯

fe|[b,c],f|[a,b], ǫo

s v w

fn+1

Fig. 5 The setting of Lemma 8.

and define feand fe′as follows:

fe:= α

¯

fe|[b,c]

fe|[b,c]+τeand fe′:= α

f|[a,b]

f|[a,b].

This yields the desired result. ⊓⊔

For the next lemma we need the definition of a flow-carrying path. Consider a

sequence P= (e1,...,en) of arcs such that the head of each arc is the tail of the next.

Notice that e1,...,enare not necessarily pairwise distinct. Let vbe the tail of e1and w

be the head of en. The arcs sequence Pis called a flow-carrying v-w-path if there exist

flows f1,...,fnassociated to arcs e1,...,en, respectively, so that |f1|=...=|fn|and

further (Pi|ei=efi)e∈Eis a v-wBorel flow.

Informally, the next lemma considers the following situation. Suppose we are able

to route flow out of a certain node vwith departure times in Si

vfor some i. Then some

of this flow can be obtained by routing flow first from sto valong a flow carrying

path with exactly iarcs and subsequently out of v. The scenario of Lemma 8 is shown

in Figure 5. To prove this, we require the following result whose proof is given in

Appendix B.

Lemma 7 Let µ1,µ2, and ν1be finite Borel measures on Rwith corresponding dis-

tribution functions M1,M2, and N1, respectively. Further, assume that |µ1| ≥ |µ2|

and ν1≤µ1. Then there exists a (finite) Borel measure ν2≤µ2with distribution func-

tion N2such that |N1(θ)−N2(θ)| ≤ |M1(θ)−M2(θ)|for each θ∈R, i.e, the vertical

distance between the distribution functions does not increase when replacing µ1and µ2

with ν1and ν2, respectively.

Lemma 8 Let fbe a nonzero measure and f≤ue|Sn

vfor some arc e= (v, w)and

some n. Then there exists a flow-carrying s-w-path P= (e1,...,en+1)with corre-

sponding flows f1,...,fn+1 containing n+ 1 arcs for which en+1 =eand fn+1 ≤f.

Proof The proof is by induction over n. Obviously, this lemma holds for n= 0. Thus

we assume that the assertion holds for n−1 (n > 0) and proceed to show that the

lemma is true for n.

Suppose that fis a nonzero measure and f≤ue|Sn

vfor some arc e= (v, w).

Lemma 6 implies the existence of some e′= (w′, v) and nonzero measures fe′and fe

such that

|fe′|=|fe|, fe′≤ue′|Sn−1

w′, fe≤f , −Lv≤(Fe′−τe′)−Fe≤Uv.

By the induction hypothesis there is a flow-carrying s-v-path P= (e1,...,en) with

corresponding Borel flows g1,...,gnfor which en=e′and gn≤fe′. Then it follows

that P′= (e1,...,en, e) with corresponding Borel flows 1

2g1,...,1

2gn,1

2gn+1 is a

flow-carrying s-w-path where gn+1 is the result of Lemma 7 with respect to fe′,fe

and gn≤fe′. Note that Lemma 7 ensures that the node capacity constraint remains

valid at node v. Also note that the division by 2 is needed in case that e=eifor

some i= 1,...,n. This concludes the proof of the lemma. ⊓⊔

Corollary 1 Suppose that the sink tis reachable in the residual network with respect

to some s-tBorel flow x. Then xis not a maximum Borel flow.

Proof We have Si∈NSi

t6=∅since the sink tis reachable. Thus there exists an n∈N

for which Sn

t6=∅and we can conclude that ur

e|Sn−1

vis nonzero for some arc e∈δ−(t).

It then follows from Lemma 8 that there is a flow-carrying s-tpath containing a finite

number of arcs. Lemma 3 implies that xis not a maximum Borel flow. ⊓⊔

7 MaxFlow-MinCut Theorem

In this section we prove the MaxFlow-MinCut Theorem for Borel flows and Borel cuts.

The basic idea of the proof is similar to the static case. Given a maximum Borel flow x,

we compute, for each v∈V, the set Svof points in time for which node vis reachable

in the corresponding residual network. We apply the Reachability Procedure on

the residual network and set Sv:= Si∈NSi

v. In the following two lemmas we show

that S:= (Sv)v∈Vis a well defined s-tBorel cut and that its capacity equals the value

of x.

Lemma 9 Suppose that xis a (maximum) s-tBorel flow and S= (Sv)v∈Vis the cor-

responding s-tBorel cut computed by the Reachability Procedure. For each v∈V,

the set Γv:= Sv∩U≻0

vcan be expressed as a countable union of pairwise disjoint in-

tervals.

Proof Let v∈V\ {s, t}be some node. Recalling the definition of the residual network

first observe that Uv=Ur

v+Lr

v. Since Uv,Ur

v, and Lr

vare functions of bounded

variation the left limit exists everywhere. Hence, we have U≻0

v=Ur,≻0

v∪Lr,≻0

Next, consider a certain iteration i−1 of the procedure and let vbe processed in the

loop of Step (3). Using the notation of the procedure, we show that Si

v∩U≻0

v=S+∪S−

holds. Since Si

v=S0∪S+∪S−and S+∪S−⊆Ur,≻0

v∪Lr,≻0

v=U≻0

vit holds that

v∩U≻0

v= (S0∩U≻0

v)∪S+∪S−.

Thus, it is enough to show that S0∩U≻0

v⊆S+∪S−. Note that S0= supp(µ1)∩¯

where ¯

A=A∪(Ur,≻0

v\S+)∪(Lr,≻0

v\S−). Because of

U≻0

v\(S+∪S−)⊆(Ur,≻0

v\S+)∪(Lr,≻0

v\S−)⊆¯

we obtain S0∩U≻0

v⊆U≻0

v∩¯

Ac⊆S+∪S−. This shows Si

v∩U≻0

v=S+∪S−.

From the above discussion, we obtain Si

v∩U≻0

v=S+∪S−. Both S+and S−are

countable unions of pairwise disjoint intervals, so Si

v∩U≻0

vis as well. As Sv=Si∈NSi

is a countable union of the sets Si

v, also Γv=Sv∩U≻0

vis a countable union of pairwise

disjoint intervals. ⊓⊔

Lemma 10 Let xbe a maximum s-tBorel flow. Then there exists an s-tBorel cut

whose capacity equals the value of x.

Proof Let S= (Sv)v∈Vbe the s-tBorel cut computed by the Reachability Proce-

dure on the residual network with respect to x. In particular, we have Ss=R. More-

over, the hypothesis of the lemma implies that St=∅since otherwise xis not maximum

by Corollary 1. Further, it follows from Lemma 9 that, for each node v∈V\ {s, t},

the set Γv:= Sv∩U≻0

vcan be written as Si∈JvIv,i, where Jvis a countable set

and Iv,i,i∈Jv, are pairwise disjoint intervals. Notice that each interval Iv,i is sup-

posed to be inclusion-wise maximal. Hence, Sis a well defined s-tBorel cut.

In the remainder of the proof we show that val(x) = cap(S). Recall from the proof

of Lemma 2 that the value of xcan be written as follows:

val(x) = X

e=(v,w)∈ExeSv∩(Sw−τe)c−xeSc

v∩(Sw−τe)

v∈V\{s,t}

X

i∈J1

vYv(βv,i−)−Yv(αv,i)+X

i∈J2

vYv(βv,i−)−Yv(αv,i−)



v∈V\{s,t}

X

i∈J3

vYv(βv,i)−Yv(αv,i)+X

i∈J4

vYv(βv,i)−Yv(αv,i−)

,

where αv,i and βv,i are the left and right boundaries of the interval Iv,i for each v∈V

and i∈N. Further, J1

v,J2

v,J3

v, and J4

vare the sets of indices ifor which Iv,i is open,

left-closed & right-open, right-closed & left-open, and closed, respectively. On the other

hand, the capacity of Sis given by

cap(S) = X

e=(v,w)∈E

ueSv∩(Sw−τe)c+

v∈V\{s,t}X

i∈J1

v∪J2

Uv(βv,i−) + X

i∈J3

v∪J4

Uv(βv,i).

Given the value of xand the capacity of Sas above, it suffices to show that the

following hold:

(i) xeSv∩(Sw−τe)c=ueSv∩(Sw−τe)cand xeSc

v∩(Sw−τe)= 0 for all

e= (v, w)∈E,

(ii) Yv(βv,i−) = Uv(βv,i−) and Yv(αv,i) = 0 for all v∈V\ {s, t}and i∈J1,

(iii) Yv(βv,i−) = Uv(βv,i−) and Yv(αv,i−) = 0 for all v∈V\ {s, t}and i∈J2,

(iv) Yv(βv,i) = Uv(βv,i) and Yv(αv,i) = 0 for all v∈V\ {s, t}and i∈J3,

(v) Yv(βv,i) = Uv(βv,i) and Yv(αv,i−) = 0 for all v∈V\ {s, t}and i∈J4.

Proof of case (i). By the definition of the residual network, (i) is equivalent to show

that ur

eSv∩(Sw−τe)c= 0 for all arcs e= (v, w)∈Erin the residual network.

Since Sv:= Sj∈NSj

vit is enough to show ur

eSj

v∩(Sw−τe)c= 0 for each j∈N.

Fix an j∈Nand consider the execution of Step (3d) for node win iteration j. We

have (using the notations of the procedure) ur

e|Sj

v−τe≤µ1. Moreover, we know from

the definition of S0that S0= supp(µ1)\¯

Aand from Lemma 5 that µ1(¯

A) = 0. This

shows that µ1(Sc

0) = 0 and consequently (ur

e|Sj

v−τe)(Sc

0) = ur

e(Sj

v∩(S0−τe)c) = 0.

Since (Sw−τe)c⊆(S0−τe)cas S0⊆Swwe can conclude ur

eSj

v∩(Sw−τe)c= 0.

Proof of the first part of (ii) and (iii). We equivalently prove that Ur

v(βv,i−) = 0

for all v∈V\ {s, t}and i∈J1∪J2in the residual network. Let β:= βv,i be the right

boundary of the right open interval Iv,i for some node v∈V\{s, t}and some i∈J1∪J2.

Note that because of the definition of βwe have β /∈Γv. We assume by contradiction

that Ur

v(β−)>0 and proceed to show that β∈Γvor that βis not the right boundary

of some inclusion-wise maximal interval of Γv.

Because of Ur

v(β−)>0 we have β∈Ur,≻0

v. Since Ur,≻0

vis the countable union

of positive intervals there exists an inclusion-wise maximal positive interval I⊆Ur,≻0

with β∈I. Note that βis not the left boundary of I(if Iis left closed) since this

would imply Ur

v(β−) = 0. Hence, the set ¯

I:= I∩(−∞, β] is a right closed interval

with nonempty interior, i.e., ¯

I\ {β} 6=∅. We first consider the case that flow can be

sent into vuntil time βover Iat some iteration of the Reachability Procedure,

i.e., µ1|¯

I>0. Recalling Step (3b), this shows that β∈S+, and therefore β∈Γv.

Next we consider the case that µ1|¯

I= 0 in each iteration which implies ¯

I∩S+=∅.

Recalling Step (3c) we know that Lr,≻0

v=Sk∈JIkis the countable union of disjoint

positive intervals. We fix a k∈Jand show that ¯

I∩Ik∩H<|hk|

k=∅. Since hk=µ1|Ik

and µ1|¯

I= 0 we have either ¯

I⊆H<|hk|

kor ¯

I∩H<|hk|

k=∅. Let us assume ¯

I⊆H<|hk|

as in the other case the assertion is trivial. Hence, if β /∈Ik, then βis on the left of Ik

since otherwise β /∈H<|hk|

kwhich contradicts our assumption ¯

I⊆H<|hk|

kdue to β∈¯

Moreover, we know that βis the right boundary of ¯

Iwhich implies ¯

I∩Ik∩H<|hk|

k=∅.

On the other hand, if β∈Ikwe obtain either β∈Ik∩H<|hk|

kor ¯

I∩Ik∩H<|hk|

k=∅.

Since Ik∩H<|hk|

k⊆S−⊆Γvholds, β∈Ik∩H<|hk|

kwould imply β∈Γvcontradict-

ing β /∈Γv.

From the above discussion, we can deduce that ¯

I∩Ik∩H<|hk|

k=∅for all k∈J.

This shows ¯

I∩S−=∅. Recall that ¯

I∩S0=∅due to ¯

I∩S+=∅and ¯

I⊆Ur,≻0

So we can conclude ¯

I∩Γv=∅. This shows that βis not the right boundary of an

inclusion-wise maximal interval of Γv, which contradicts the definition of β. Hence, we

must have Ur

v(β−) = 0, which establishes the first part of (ii) and (iii).

Proof of the first part of (iv) and (v). Equivalently we show that Ur

v(βv,i) = 0

for all v∈V\ {s, t}and i∈J3∪J4in the residual network. Let β:= βv,i be the

right boundary of the right closed interval Iv,i for some node v∈V\ {s, t}and

some i∈J3∪J4. Note that because of the definition of βwe have β∈Γv. We

assume Ur

v(β)>0 and proceed to derive a contradiction.

Because of Ur

v(β)>0 we have β∈Ur,≻0

v. Since Ur,≻0

vis the countable union of

positive intervals there exists an inclusion-wise maximal positive interval I⊆Ur,≻0

with β∈I. Note that βis not the right boundary of I, since otherwise we must

have Ur

v(β) = 0. We define the set ¯

I:= I∩(−∞, β]. Note that ¯

I={β}if Ur,≻0

v(β−) = 0.

As above, we first consider the case that µ1|¯

I>0. Recalling Step (3b), this shows

that I∩[β, ∞)⊂S+and as a consequence I∩[β, ∞)⊂Γv. This implies that βis not

the right boundary of some inclusion-wise maximal interval of Γv. Next we consider

the case that µ1|¯

I= 0 in each iteration which implies ¯

I∩S+=∅. Here it follows along

the same line as above that βis not the right boundary of an inclusion-wise maximal

interval of Γv. This contradicts the definition of β. Hence, we must have Ur

v(β) = 0.

Proof of the second part of (ii) and (iv). It is equivalent to show that Lr

v(αv,i) = 0

for all v∈V\ {s, t}and i∈J1∪J3in the residual network. Let α:= αv,i be the left

boundary of the left open interval Iv,i for some node v∈V\{s, t}and some i∈J1∪J3.

By the definition of αwe have α /∈Γv. We assume by contradiction that Lr

v(α)>0 and

proceed to show that α∈Γvor that αis not the left boundary of some inclusion-wise

maximal interval of Γv.

We have α∈Lr,≻0

vas Lr

v(α)>0. Since Lr,≻0

vis the countable union of positive

intervals there exists an inclusion-wise maximal positive interval I⊆Lr,≻0

vwith α∈I.

Note that αis not the right boundary of Isince otherwise we must have Lr

v(α) = 0.

Hence, the set ¯

I:= I∩[α, ∞) is a left closed interval with ¯

I\ {α} 6=∅. Let us first

consider the case that flow can be sent into von or after time αover Iat some

iteration of the Reachability Procedure, i.e., µ1|¯

I>0. Recalling Step (3c), this

implies α∈S−, and therefore α∈Γv.

We now assume that µ1|¯

I= 0 in each iteration which implies ¯

I∩S−=∅. Recalling

Step (3b) we know that Ur,≻0

v=Sk∈JIkis the countable union of disjoint positive

intervals. We fix an arbitrary k∈Jand show that ¯

I∩Ik∩H>0

k=∅. Since hk=µ1|Ik

and µ1|¯

I= 0 we have either ¯

I⊆H>0

kor ¯

I∩H>0

k=∅. We assume ¯

I⊆H>0

k, as in

the other case the assertion is trivial. Hence, if α /∈Ik, then αis on the right of Ik

since otherwise α /∈H>0

kwhich contradicts our assumption ¯

I⊆H>0

kdue to α∈¯

Moreover, we know that αis the right boundary of ¯

Iwhich implies ¯

I∩Ik∩H>0

k=∅.

On the other hand, if α∈Ikwe get either α∈Ik∩H>0

kor ¯

I∩Ik∩H>0

k=∅.

Since Ik∩H>0

k⊆S+⊆Γvholds, α∈Ik∩H>0

kwould imply α∈Γvcontradicting the

fact that α /∈Γv.

Now we can deduce that ¯

I∩Ik∩H>0

k=∅for all k∈J. This implies ¯

I∩S+=∅.

Recall that ¯

I∩S0=∅due to ¯

I∩S−=∅and ¯

I⊆Lr,≻0

v. So we can conclude ¯

I∩Γv=∅.

This shows that αis not the left boundary of an inclusion-wise maximal interval of Γv,

which contradicts the definition of α. Hence, we must have Lr

v(α) = 0, which establishes

the second part of (ii) and (iv).

Proof of the second part of (iii) and (v). It is equivalent to show that Lr

v(αv,i−) = 0

for all v∈V\ {s, t}and i∈J1∪J3in the residual network. Let α:= αv,i be the left

boundary of the closed interval Iv,i for some node v∈V\ {s, t}and some i∈J2∪J4.

By the definition of αwe have α∈Γv. We assume by contradiction that Lr

v(α−)>0

and seek a contradiction.

We have α∈Lr,≻0

vas Lr

v(α−)>0. Then there exists an inclusion-wise maximal

positive interval I⊆Lr,≻0

vwith α∈I. Note that αis not the left boundary of I.

We consider the set ¯

I:= I∩[α, ∞). We may have ¯

I={α}if Lr

v(α) = 0. Let us

first consider the case that flow can be sent into von or after time αover Iat some

iteration of the Reachability Procedure, i.e., µ1|¯

I>0. Recalling Step (3c), this im-

plies (−∞, α]∩I⊂S−, and therefore v⊂Γv. We now consider the case that µ1|¯

I= 0

in each iteration which implies ¯

I∩S−=∅. In this case, in a similar way as in the

proof of the second part of (ii) and (iv) to show that αis not the left boundary of an

inclusion-wise maximal interval of Γv, which contradicts the definition of α. Hence, we

must have Lr

v(α−) = 0. ⊓⊔

Theorem 2 For an s-tBorel flow xthe following statements are equivalent:

(i) The s-tBorel flow xis maximal.

(ii) There is no flow-carrying s-tpath in the residual network with respect to x.

(iii) The sink tis not reachable in the residual network with respect to x.

Proof Following the proof of Corollary 1 we obtain the two implications (i) =⇒(ii)

and (ii) =⇒(iii). In particular, the implication (i) =⇒(ii) follows form Lemma 3.

To see that (iii) =⇒(i) holds let S= (Sv)v∈Vbe the Borel cut computed by the

Reachability Procedure. Since tis not reachable, Sis an s-tBorel cut. Moreover,

by Lemma 10, we have cap(S) = val(x). It then follows from Lemma 2 that xis

maximum. ⊓⊔

Combining Theorem 1 and Lemma 10 we get the main result of this paper.

Theorem 3 (MaxFlow-MinCut Theorem) There exists an s-tBorel flow xand

an s-tBorel cut Sfor which val(x) = cap(S).

Throughout the paper, we have considered the entire real line Ras the time in-

terval. However, all results remain valid if a time horizon T > 0 is given and the

initial time is supposed to be zero, that is, flow originates at the source on or af-

ter time zero and must reach the sink strictly before time T. In this case, a Borel

cut S= (Sv)v∈Vis called an s-tcut if Ss= [0,∞) and St:= [T, ∞). To deal

with this case, we introduce a source s0connected to swith an arc (s0, s) and a

sink t0connected to twith an arc (t, t0). We assign a transit time of zero to both

arcs (s0, s) and (t, t0), a capacity u(s0,s):= Pe∈δ+(s)ue|[0,∞)to arc (s0, s) and ca-

pacity u(t,t0):= Pe∈δ−(t)ue|(−∞,T )to arc (t, t0). Further, we let Us=Ut=∞

and Ls=Lt= 0. Then any s-tBorel flow obeying the additional departure and

arrival time restrictions corresponds one-to-one to an s-tBorel flow on the constructed

instance. Hence, an instance of (MBFP) with time horizon Tand initial time 0 can be

converted to an equivalent problem without time restrictions on the extended network.

Therefore, all results can be translated to this situation as follows:

Theorem 4 Consider an instance of (MBFP) with initial time 0 and time horizon T

and let xbe an s-tBorel flow on this instance. Then following statements are equivalent:

(i) The s-tBorel flow xis maximal.

(ii) There exists no flow-carrying s-tpath in the residual network with respect to x

along which flow is able to arrive at tstrictly before time T.

(iii) The sink tis not reachable in the residual network with respect to xbefore time T.

(iv) There exists an s-tBorel Scut with cap(S) = val(x).

8 Conclusion and future work

We introduced the notion of Borel flows to unify discrete and continuous network

flows over time into a single model. We focused on the Maximum Borel Flow Problem

(MBFP) and gave a theoretical analysis of this problem, leading to a MaxFlow-MinCut

Theorem. Our approach is based on a so-called Reachability Procedure, which is

used to verify wether or not a given Borel flow xis maximal. Further, if xis not max-

imal, we can derive an augmenting s-tpath. Sending flow along this path leads to a

new s-tBorel flow with strictly larger value. Thus, the Reachability Procedure

lays the ground for an algorithmic approach. Like the augmenting path algorithm for

the static maximum flow problem, the algorithm maintains a feasible solution at each

iteration and successively improves the solution towards optimality. More specifically,

the algorithm starts with the zero flow x. Then, by calling the Reachability Pro-

cedure as a subroutine, it identifies augmenting s-tpaths and sends flow along these

paths, while preserving feasibility. The algorithm terminates when the sink tis not

reachable any more. Corollary 1 implies that upon the termination of the algorithm it

has found a maximum s-tBorel flow.

The problem arising in the implementation of the algorithm for computing a max-

imum Borel flow is that, in general, the procedure never terminates and even requires

infinite memory if the node and arc capacities have pathological structure. This makes

the procedure problematic for computing a maximum Borel flow. Hence the question

under which circumstances the procedure is a finite-time algorithm is of great interest

and certainly deserves attention. For example, if the arc capacities are concentrated on

a finite set and no restrictions on storage at nodes are made, then the Reachability

Procedure terminates in finite time. This remains also true if we forbid storage at

nodes, i.e., if we set all node capacities to zero, but in general we need an oracle decid-

ing wether flow can be stored between two given points in time or not. In general, one

has to examine the following aspects in developing a finite algorithm for computing a

maximum flow: the decomposition of the sets U≻0

vand L≻0

vin Steps (3b) and (3c),

respectively, into a countable union of disjoint positive intervals, Lebesgue decomposi-

tion of measure µ1in Step (3d) (note that there is a constructive proof), the number

of iterations within the Reachability Procedure, and the number of calls of the

Reachability Procedure. Further details are beyond the scope of the paper and are

left for future work.

We conclude the paper by considering a possible extension of a MaxFlow-MinCut

Theorem to the more general setting of time/inflow/Load-dependent transit times.

In (MBFP), although arc and node capacities are subject to fluctuations over time, the

transit times are constant. A natural generalization of (MBFP) is the case where tran-

sit times are time-dependent (that is, the transit time of an arc depends on the time a

flow enters the arc) or inflow-dependent (that is, the transit time of an arc depends on

the amount of flow entering the arc). However, in many real-world applications, such as

road traffic control, production systems, and communication networks, a difficult but

more realistic feature is that the amount of time needed to traverse an arc increases

as the arc becomes more congested. Introducing this into (MBFP) leads to the case of

load-dependent transit times (that is, transit time of an arc is not necessarily constant

but depends on the amount of flow currently sent on the arc). These generalizations

of (MBFP) make the problem much harder to analyze and require a more complicated

formulation. The basic problem arising here is whether or not the MaxFlow-MinCut

Theorem holds in these more general settings. This problem is theoretically interesting

and certainly deserves further study.

Acknowledgment

The authors are much indebted to an anonymous referee for numerous valuable com-

ments that helped to improve the presentation of the paper.

References

1. E. J. Anderson and P. Nash. Linear Programming in Infinite-Dimensional Spaces. Wiley,

New York, 1987.

2. E. J. Anderson, P. Nash, and A. B. Philpott. A class of continuous network flow problems.

Mathematics of Operations Research, 7:501–514, 1982.

3. T. M. Apostol. Mathematical Analysis. 2th Edition, Addison-Wesley, 1974.

4. J. E. Aronson. A survey of dynamic network flows. Annals of Operations Research,

20:1–66, 1989.

5. J. B. Conway. A Course in Functional Analysis. 2nd Edition, New York, Springer-Verlag,

1990.

6. L. K. Fleischer and ´

E. Tardos. Efficient continuous-time dynamic network flow algorithms.

Operations Research Letters, 23:71–80, 1998.

7. L. R. Ford and D. R. Fulkerson. Constructing maximal dynamic flows from static flows.

Operations Research, 6:419–433, 1958.

8. L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.

9. J. F. C. Kingman and S. J. Taylor. Introduction to Measure and Probability. Cambridge

University Press, Cambridge, 1966.

10. B. Kotnyek. An annotated overview of dynamic network flows. Rapport de recherche

4936, INRIA Sophia Antipolis, 2003.

11. S. E. Lovetskii and I. I. Melamed. Dynamic network flows. Automation and Remote

Control, 48:1417–1434, 1987. Translated from Avtomatika i Telemekhanika, 11 (1987),

pp. 7–29.

12. E. Nasrabadi. Dynamic Flows in Time-varying Networks. PhD thesis, Technische Uni-

versit¨at Berlin, Berlin, 2009.

13. K. R. Parthasarathy. Probability Measures On Metric Spaces. Academic Press, New York,

1967.

14. A. B. Philpott. Algorithms For Continuous Network Flow Problems. PhD thesis, Univer-

sity of Cambridge, UK, 1982.

15. A. B. Philpott. Continuous-time flows in networks. Mathematics of Operations Research,

15:640–661, 1990.

16. A. B. Philpott. Continuous-time shortest path problems and linear programming. SIAM

Journal on Control and Optimization, 32:538–552, 1994.

17. W. B. Powell, P. Jaillet, and A. Odoni. Stochastic and dynamic networks and routing. In

M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, editors, Network Routing,

volume 8 of Handbooks in Operations Research and Management Science, chapter 3, pages

141–295. North–Holland, Amsterdam, The Netherlands, 1995.

18. M. Skutella. An introduction to network flows over time. In W. Cook, L. Lov´asz, and J. Vy-

gen, editors, Research Trends in Combinatorial Optimization, pages 451–482. Springer,

Berlin, 2009.

A Preliminaries on measure theory

In this appendix we present some definitions and notations that are frequently used throughout

the paper. For a detailed treatment we refer to, e.g., [9,13].

Aσ-algebra on the real line Ris a nonempty collection of subsets of Rthat is closed under

countable unions and complements. The smallest σ-algebra on Rcontaining all open sets (or,

equivalently, closed sets) is called the Borel σ-algebra. The elements of the Borel algebra are

called measurable sets or Borel sets. Let Bdenote the collection of all Borel sets on R. A

function µ:B → R≥0is called a Borel measure on Rif

(i) µ(∅) = 0 ,

(ii) µ(B)≥0 for any B∈ B ,

(iii) let {Bi}i∈Nbe a countable collection of pairwise disjoint sets in B, then

µ[

i∈N

Bi=X

i∈N

µ(Bi).

Measures are by definition nonnegative, i.e., a nonnegative real number is assigned to each

measurable set. However, it is sometimes convenient to allow that a measure also takes negative

values. A measure which can take negative and positive values is called a signed measure. The

space of finite signed measures becomes a vector space under the standard addition and scalar

multiplication operations. In particular, for any two finite signed Borel measures µ1and µ2

and any real value λ, the addition µ1+µ2and scalar multiplication λ·µ1are defined as

(µ1+µ2)(B) = µ1(B) + µ2(B)∀B∈ B ,

(λ·µ1)(B) = λ·µ1(B)∀B∈ B .

We use also 0 to denote the null element of this vector space, i.e., the measure which assigns 0

to each B∈ B. For a signed Borel measure µ, a Borel set Bis called a µ-null set if µ(B) = 0

and a strict µ-null set if µ(A) = 0 for all A⊆B. Note that if µis not a signed measure then

both definitions coincide.

Let Mbe a real-valued function on R. The total variation of Mwithin the interval [a, b]

is defined by

V(M; [a, b]) := supnn

i=2

M(ai)−M(ai−1)| {a1, . . . , an}is a partition of [a, b]o.

The function Mis said to be of bounded variation on Rif there exists a constant K < ∞

such that V(M; [a, b]) < K for any (finite) interval [a, b]⊂R. It is a well-known result that

a function is of bounded variation if and only if it is the difference between two monotonic

increasing functions (see, e.g., Chapter 6 in [3]).

A function M:R→Ris called a distribution function if it is of bounded variation, continu-

ous from right, and M(−∞) = 0. A Borel measure µon Ris called finite if the norm |µ|:= µ(R)

of µis finite, i.e., |µ|<∞. It is well known that the formula µ(−∞, b]=M(b) sets up a

one-to-one correspondence between finite signed Borel measures and distribution functions. In

particular, if µis a nonnegative measure, then its corresponding distribution function Mis

monotonic increasing. Throughout the paper, we denote the measures by small letters (such

as µ,ν,f,y,z,u,h) and their corresponding distribution functions by capital letters (such

as M,N,F,Y,Z,U,H).

Let µ1and µ2be two signed Borel measures, respectively, with corresponding distribution

functions M1and M2. We write µ1=µ2(µ1≤µ2) if µ1(B) = µ2(B) (µ1(B)≤µ2(B)) for

each B∈ B. We also write M1≤M2if M1(θ)≤M2(θ) for each θ∈R. Note that µ1≤µ2

implies M1≤M2but the other direction does not hold in general.

Suppose that µis a Borel measure with corresponding distribution function M. For a

measurable set A, the restriction µ|Aof µto Ais a measure defined by µ|A(B) := µ(B∩A) for

each B∈ B. Hence Ais a strict µ-null set if µ|A= 0. Moreover, the restriction M|A:A→R

of Mis defined by θ7→ M(θ) for all θ∈A. Note that M|Ais not a distribution function since

it is not defined on the whole real line Rand, in particular, it is not the distribution function

of µ|A. In addition, we write M|A> ǫ for some ǫif M(θ)> ǫ for all θ∈A.

Moreover, for a real value τwe define the shifted measure µ−τby (µ−τ)(B) = µ(B−τ)

for each B∈ B, where B−τ:= {θ−τ|θ∈B}. Similarly, the shifted function M−τ:R→R

of Mis defined by θ7→ M(θ−τ). Note that M−τis the distribution function of µ−τ.

For the distribution function M, we define M≻0(M>0and M<|µ|) to denote the set of

all points θ∈Rsuch that Mor its left limit is positive at θ(M(θ)>0 and M(θ−)<|µ|,

respectively). More precisely,

M≻0:= θ∈R|M(θ−)>0 or M(θ)>0,

M>0:= θ∈R|M(θ)>0,

M<|µ|:= θ∈R|M(θ−)<|µ|.

Note that if Mis a distribution function of a nonnegative measure, then M≻0=M>0. Since M

is right continuous M≻0is the countable union of pairwise disjoint intervals. Moreover, we can

assume that each interval Iof the countable union is positive, i.e., for all a, b ∈Iwith a < b

there exists an ǫ > 0 such that M|[a,b)> ǫ (see Lemma 4). Throughout the paper we implicitly

assume that each (positive) interval is inclusion-wise maximal.

Given a Borel measure µ, the support of µis defined to be the set of all points in Rwith

a neighborhood of positive measure, that is,

supp(µ) := θ∈R|µ(I)>0 for every open neighborhood Iof θ.

A point θ∈Ris called an atom of µif µ({θ})>0. Obviously, if µis finite, the set of atoms

of µis countable. In this case, we define the discrete part µdand continuous part µcof µby

µd(B) := X

atoms θ∈B

µ{θ}and µc(B) := µ(B)−µd(B)

for every measurable set B.

A measure µis called discrete (continuous1) if its continuous (discrete) part is zero. It can

be shown that a finite Borel measure is continuous (discrete) if and only if its corresponding

distribution function is a continuous function (a step function) (see, e.g., [9, Section 9.3]).

Hence, there is a decomposition of a finite Borel measure into a sum of a discrete and a

continuous measure. This decomposition is unique.

A measure µis said to be concentrated on a measurable set Aif µ(B) = 0 whenever

A∩B=∅for each measurable set B. We can easily see that a finite measure is concentrated

on a countable set if and only if it is discrete.

Two Borel measures µ1and µ2are called mutually singular if there exist two disjoint

measurable sets Aand Bwhose union is Rsuch that µ1is zero on all measurable subsets of B

1A continuous measure is also called nonatomic measure.

while µ2is zero on all measurable subsets of A, i.e., µ1(B) = 0 and µ2(A) = 0. Moreover, µ1is

absolutely continuous with respect to µ2if µ2(A) = 0 implies µ1(A) = 0 for every measurable

set A.

The following theorem shows that any signed measure can be expresses as the difference

of two mutually singular measures (see, e.g., [9] for a proof).

Theorem 5 (Jordan Decomposition) Every signed measure µcan be expressed as the

difference of two (nonnegative) measures µ+and µ−such that µ+and µ−are mutually

singular and at least one of them is finite. If µis finite, then both µ1and µ2are finite.

Moreover, if µ=µ1−µ2, then µ+≤µ1and µ−≤µ2. The measures µ+and µ−are

called the positive and negative part of µ, respectively. The pair (µ+, µ−)is called the Jordan

decomposition of µ.

Theorem 5 helps us to define the minimum of two measures. Let µ1and µ2be two non-

negative measures on R. The minimum of µ1and µ2is a nonnegative measure defined by

min{µ1, µ2}:= µ1−µ+=µ2−µ−, where (µ+, µ−) is the Jordan decomposition of the signed

measure µ1−µ2. It is not hard to see that min{µ1, µ2}is positive if µ1and µ2are positive

and not mutually singular. In particular, if µ2is positive and µ2is absolutely continuous with

respect to µ1, then min{µ1, µ2}is positive.

We also need the following basic theorem of measure theory (see, e.g., [9] for a proof).

Theorem 6 (Lebesgue Decomposition) Suppose that µ1and µ2are two finite Borel mea-

sures. There exist two finite Borel measures νac and νssuch that

–µ2=νac +νs;

–νac is absolutely continuous with respect to µ1;

–νsand µ1are mutually singular.

The proof of the Lebesgue Decomposition Theorem is constructive and the measures νac

and νsare constructed through the proof. The construction also gives a set Asuch that

µ1(A) = 0 and νs(Ac) = 0.

B Proof of technical lemmas

In this Appendix, we provide the proofs of Lemmas 1, 4 and, 7 that were omitted from the main

text. The proof of Lemma 1 is based on the next lemma together with the two subsequently

corollaries.

Lemma 11 Suppose that µ1and µ2are two finite continuous Borel measures on Rwith

distribution functions M1and M2, respectively. Let M1≥M2on some interval I:= (−∞, θ],

θ∈R, and A:= {ϑ∈I|M1(ϑ) = M2(ϑ)}be the set of points in Iwhere the two distribution

functions are equal. Then µ1(A) = µ2(A).

Proof For a given ǫ > 0, let Aǫ:= {ϑ∈(−∞, θ)|M1(ϑ)−M2(ϑ)< ǫ}be the set of

points in (−∞, θ) where the two distribution functions differ by less than ǫ. We know that the

distribution functions M1and M2are continuous since µ1and µ2are continuous measures.

Hence, Aǫis an open set, so we can express it as a countable union of pairwise disjoint open

intervals: Aǫ=Si∈J(ai, bi), where Jis a countable set of indices and ai=−∞ for one i∈J.

Note that, for each i∈J, the interval (ai, bi) is maximal in the following sense. There exists

no open interval (a′, b′)⊆Aǫstrictly containing (ai, bi). Since the distribution functions M1

and M2are continuous we can conclude that

M1(ai)−M2(ai) = (ǫif ai>−∞

0 if ai=−∞ and M1(bi)−M2(bi)(=ǫif bi< θ

≤ǫif bi=θ.

It follows that

µ1(Aǫ)−µ2(Aǫ) = X

i∈J

µ1(ai, bi)−µ2(ai, bi)≤ǫ .

Now we let ǫtend to 0 and get µ1(A\ {θ}) = µ2(A\ {θ}). Since µ1and µ2are continuous this

shows µ1(A) = µ2(A). ⊓⊔

The next corollary generalizes Lemma 11 from µ1(A) = µ2(A) to µ1|A=µ2|A, even for

the more general case when the assumption of M1≥M2is not met.

Corollary 2 Let µ1and µ2be two finite continuous Borel measures on Rwith distribution

functions M1and M2, respectively. Further, let A:= {θ∈R|M1(θ) = M2(θ)}be the set of

points where the two distribution functions are equal. Then, µ1|A=µ2|A.

Proof We first assume that M1≥M2. Then, Lemma 11 implies

µ1|A(−∞, θ]=µ1|(−∞,θ](A) = µ2|(−∞,θ](A) = µ2|A(−∞, θ],for all θ∈R.

It follows from this relation that the distribution functions with respect to µ1|Aand µ2|A

coincide on R. This implies µ1|A=µ2|A.

For the general case, we define Mmax :R→Rby Mmax(θ) := max{M1(θ), M2(θ)}. It is

clear that Mmax is monotonically increasing and continuous. So it is the distribution function

of some finite continuous measure µmax. Applying the previous result for Mmax and M1, and

also for Mmax and M2, we get µ1|A=µmax|A=µ2|A.⊓⊔

Corollary 3 Let µbe a finite signed Borel measure on Rwith distribution function Mand

let Q⊂Rbe a countable set of real numbers. If µis continuous, then A:= {θ|M(θ)∈Q}is

a strict µ-null set, i.e., µ|A= 0.

Proof For each q∈Qdefine Aq:= {θ|M(θ) = q}. Since Ais the disjoint countable union of

the sets Aq, we have µ|A=Pq∈Qµ|Aq. Hence, in order to establish the lemma it is enough

to show that µ|Aq= 0 for each q∈Q.

Let q∈Qbe fixed and assume, without loss of generality, that q≥0. Further, let µ+

and µ−be the positive and negative part of µwith distribution functions M+and M−,

respectively. Since µis continuous, a:= min{θ|M+(θ)≥q} ∈ R∪ {∞} is well-defined

and M+(a) = q. We define ¯

M:R→R+by

M(θ) := (0 if θ < a ,

M+(θ)−qif θ≥a .

Then, ¯

Mis the distribution function of the measure ¯µ:= µ+|[a,∞). Further, defining the

set ¯

Aqby ¯

Aq:= {θ|¯

M(θ) = M−(θ)}, Corollary 2 shows ¯µ|¯

Aq=µ−|¯

Aq. Since M(θ) = q

implies M+(θ)−M−(θ) = qit holds that Aq⊆¯

Aq. Together with Aq∩(−∞, a) = ∅it follows

that µ+|Aq= ¯µ|Aq=µ−|Aqand, as a direct consequence, µ|Aq= 0. ⊓⊔

We can now give a proof of Lemma 1.

Lemma 1 Let µbe a finite signed Borel measure on Rwith a nonnegative distribution

function M. Let A:= R\M≻0be the set of points θ∈Rfor which Mis continuous and zero

at θ. Then µ|A= 0, i.e., the set Ais a strict µ-null set.

Proof Let µdbe the discrete part of µand Mdbe its distribution function. As µis finite, the

support of µdis countable, and thus the set Q={Md(θ)|θ∈R}is countable.

Let Mcbe the distribution function of the continuous part µcand define the set ¯

by ¯

A:= {θ| −Mc(θ)∈Q}. It now follows from Corollary 3 that µc|¯

A= 0 since Qis count-

able. On the other hand, we know that A⊆¯

Aand A∩supp(µd) = ∅implying µ|A= 0. This

concludes the proof. ⊓⊔

Next we prove Lemma 4 which shows that M≻0is a countable union of pairwise disjoint

positive intervals. Recall that an interval Iis called positive if for all a, b ∈Iwith a < b there

exists an ǫ > 0 such that M|[a,b)> ǫ.

Lemma 4 Let Mbe a distribution function. Then the set M≻0, defined by (5), can be written

as a countable union of pairwise disjoint positive intervals.

Proof The set M≻0can be written as the union of two disjoint sets M≻0

con and M≻0

dis , where

M≻0

con := {θ∈M≻0|M(θ−) = M(θ)>0},

M≻0

dis := {θ∈M≻0|M(θ−)6=M(θ)}.

The set M≻0

con is an open set and hence can be expressed as the countable union of pairwise

disjoint intervals. We thus let M≻0

con =Si∈Jcon Iiwhere Jcon is a countable set of indices

and Iiis an open interval for each i∈Jcon. For each i∈J, we have M|Ii>0 and hence, Iiis

positive.

We next consider the set M≻0

dis . Each member of this set is a discontinuous point of M.

On the other hand, since Mis right-continuous, it has a countable number of discontinuous

points (see, e.g., [3]). Thus, M≻0

dis is a countable set. So let M≻0

dis =Si∈Jdis {ai}where Jdis is

a countable set of indices and aiis a real number for each i∈Jdis. For each aithere exists

an interval Ijfor some j∈Jcon such that either aiis the right boundary of some Ijand

M(ai−)>0 or otherwise it must be M(ai−) = 0 and aiis the left boundary of Ij. We then

extent Ijas Ij:= Ij∪ {ai}. Note that Ijremains positive.

The above construction gives a decomposition of M≻0into a countable union of pairwise

disjoint positive intervals Ii,i∈Jcon.⊓⊔

For the proof of Lemma 7, we need the concept of regularity for measures and a simple

result. A Borel measure µis called regular if for every Borel set B

µ(B) = sup{µ(C)|C⊆B, C closed}= inf{µ(O)|B⊆O, O open}.

It is well known that any finite Borel measure on Ris regular (see, e.g., [13]). Using the result,

the following lemma can be established.

Lemma 12 Let µand νbe two finite Borel measures on Rwith distribution functions M

and N, respectively. Then µ≤νif and only if M(b)−M(a)≤N(b)−N(a)for all a, b ∈R

with a≤b.

Proof Assume µ≤ν. Then, for all a, b ∈Rwith a≤b, it holds that M(b)−M(a) = µ((a, b]) ≤

ν((a, b]) = N(b)−N(a). Hence, it remains to prove the other direction.

Let B∈ B be any Borel set. Since every finite Borel measure on Ris regular (see, e.g., [13])

we know ν(B) = inf{ν(O)|B⊆O, O open}. Hence, for every ǫ > 0 there exists an open set O

containing Bsuch that ν(O)≤ν(B) + ǫ. Since Ois open it is the countable union of disjoint

open intervals, i.e., O=Si∈J(ai, bi) for some countable set Jand ai, bi∈R∪ {−∞,∞}.

Assuming M(b)−M(a)≤N(b)−N(a) for all a, b ∈Rwith a≤bwe have:

µ((ai, bi)) = lim

bրbi

M(b)−M(ai)≤lim

bրbi

N(b)−N(ai) = µ((ai, bi)) ∀i∈J .

This shows µ(O)≤ν(O). Since B⊆Othis implies µ(B)≤µ(O)≤ν(O)≤ν(B) + ǫ. Now we

let tend ǫto zero and obtain µ(B)≤ν(B). ⊓⊔

Using the last lemma we are able to prove Lemma 7.

Lemma 7 Let µ1,µ2, and ν1be finite Borel measures on Rwith corresponding distribution

functions M1,M2, and N1, respectively. Further, assume that |µ1| ≥ |µ2|and ν1≤µ1.

Then there exists a (finite) Borel measure ν2≤µ2with distribution function N2such that

|N1(θ)−N2(θ)| ≤ |M1(θ)−M2(θ)|for each θ∈R, i.e, the vertical distance between the

distribution functions does not increase when replacing µ1and µ2with ν1and ν2, respectively.

Proof We define ν2via its distribution function N2. The key idea is to construct N2such

that the horizontal distance between the distribution functions is preserved. That is, for

each θ1, θ2∈Rwith M1(θ1) = M2(θ2) it holds that N1(θ1) = N2(θ2). Since a measure can be

interpreted as the slope of its distribution function, ν1≤µ1ensures that the vertical distance

between the distribution functions does not increase. Unfortunately, N2is not well-defined in

this manner because the distribution functions have jumps in general.

In order to construct N2, let θ2∈Rbe some real number. Further, let θ1∈Rbe such that

M1(θ1−)≤M2(θ2)≤M1(θ1).(14)

Note that such a real number θ1exists since we know that M1(−∞) = M2(−∞) = 0 and

that M1(∞) = |µ1| ≥ |µ2|=M2(∞). Then we define:

N2(θ2) := (N1(θ1) if µ1({θ1}) = 0

N1(θ1−) + ν1({θ1})

µ1({θ1})(M2(θ2)−M1(θ1−)) if µ1({θ1})>0.(15)

Note that µ1({θ1}) and ν1({θ1}) are the heights of a jump of M1and N1at θ1, respectively.

So if µ1({θ1})>0 then N2(θ2) is defined in such a way that N2(θ2) divides the jump ν1({θ1})

of N1with the same ratio as M2(θ2) divides the jump µ1({θ1}) of M1.

Furthermore, note that although the definition of N2(θ2) depends on some θ1satisfy-

ing (14), it is independent on a special choice of θ1. This can be seen as follows: First re-

call that M1is monotonically increasing and right-continuous. Hence, if θ1is not unique

then θ1must be taken out of some closed interval I:= [a, b] satisfying M1(θ1) = M2(θ2) for

all θ1∈[a, b). Since ν1≤µ1by the hypothesis of the lemma, also N1must be constant to

some value kover [a, b) as desired. Thus using (15) we obtain N2(θ2) = kfor all θ1∈[a, b].

Hence, N2(θ2) is well-defined.

Alternatively, N2(θ2) can be defined in terms of M1(θ1) and N1(θ1), instead of M1(θ1−)

and N1(θ1−), respectively. This can be achieved by substituting M1(θ1−) = M1(θ1)−µ1({θ1})

and N1(θ1−) = N1(θ1)−ν1({θ1}) in (15) leading to:

N2(θ2) = N1(θ1) + ν1({θ1})

µ1({θ1})(M2(θ2)−M1(θ1)) .(16)

Next we show some relations which we use subsequently to show that ν2can defined

via N2. Since θ1was chosen such that (14) holds we have 0 ≤M2(θ2)−M1(θ1−)≤µ1({θ1}).

Then, the definition of N2in (15) implies that (14) holds also for N1and N2instead of M1

and M2, that is,

N1(θ1−)≤N2(θ2)≤N1(θ1).(17)

Since we assume ν1≤µ1we know ν1({θ1})≤µ1({θ1}). Further we get from (14) the inequal-

ities 0 ≤M2(θ2)−M1(θ1−) and 0 ≥M2(θ2)−M1(θ1). Hence, (15) and (16) show

N2(θ2)≤N1(θ1−) + M2(θ2)−M1(θ1−) (18)

and −N2(θ2)≤ − N1(θ1)−M2(θ2) + M1(θ1),(19)

respectively.

Now we show that N2is the distribution function of some Borel measure ν2. First we show

that N2is monotonically increasing. Let θ′

2, θ′′

2∈Rwith θ′

2< θ′′

2and let θ′

1and θ′′

1be such

that M1(θ′

1−)≤M2(θ′

2)≤M1(θ′

1) and M1(θ′′

1−)≤M2(θ′′

2)≤M1(θ′′

1). Since M1and M2are

monotonically increasing we can choose θ′

1and θ′′

1such that θ′

1≤θ′′

1. If θ′

1=θ′′

1then the

inequality N2(θ′

2)≤N2(θ′′

2) follows from M2(θ′

2)≤M2(θ′′

2). On the other hand, if θ′

1< θ′′

then N2(θ′

2)≤N2(θ′′

2) follows from (17) and the fact that N1is monotonically increasing. For

proving the right-continuity we use ν1≤µ1, (18), and (19) to obtain:

N2(θ′′

2)−N2(θ′

2)≤N1(θ′′

1−) + M2(θ′′

2)−M1(θ′′

1−)−N1(θ′

1)−M2(θ′

2) + M1(θ′

=ν1([θ′

1, θ′′

1)) −µ1([θ′

1, θ′′

1)) + M2(θ′′

2)−M2(θ′

2) (20)

≤M2(θ′′

2)−M2(θ′

2).

Since N2is monotonically increasing and M2is right-continuous, (20) shows that N2is right-

continuous (let θ′′ tend to θ′). Hence, N2is a distribution function and defines a Borel mea-

sure ν2.

Lemma 12 and equation (20) show ν2≤µ2. Hence, it remains to show that the vertical dis-

tance does not increase, i.e., for all θ2∈Rit holds that |N1(θ2)−N2(θ2)|≤|M1(θ2)−M2(θ2)|.

First we assume that 0 ≤M1(θ2)−M2(θ2). From the definition of θ1we obtain the chain

of inequalities M1(θ1−)≤M2(θ2)≤M1(θ2). Since M1is monotonically increasing this im-

plies θ1≤θ2. Thus, we obtain with (19) and ν1≤µ1:

0≤N1(θ2)−N2(θ2) = N1(θ2)−N1(θ1)−M2(θ2) + M1(θ1−)

≤M1(θ2)−M1(θ1)−M2(θ2) + M1(θ1−) = M1(θ2)−M2(θ2)

Hence, we have |N1(θ2)−N2(θ2)| ≤ |M1(θ2)−M2(θ2)|in the case of 0 ≤M1(θ2)−M2(θ2).

If M1(θ2)−M2(θ2)≤0, we can follow the same line of arguments as above and we therefore

omit the details. This completes the proof. ⊓⊔