# Balanced Submodular Flows

Alpár Jüttner  Department of Operations Research, Eötvös Loránd University,
Budapest, Hungary.
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>Eszter Szabó
Department of Operations Research, Eötvös Loránd University, Budapest,
Hungary.
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
> Abstract: This paper examines the Balanced Submodular Flow Problem, that is
> the problem of finding a feasible submodular flow minimizing the difference
> between the flow values along the edges. A min-max formula is given to the
> problem and an algorithm is presented to solve it using $\mathcal{O}(m^{2})$
> submodular function minimizations. Then, these results are extended to the
> weighted version of the problem. Finally, the Balanced Integer Submodular
> Flow Problem is discussed.

> Keywords: submodular flow, balanced optimization, strongly polynomial
> algorithm

##  1 Introduction

Balanced optimization problems aim to find a most equitable distribution of
resources. Several problems have been analysed in the literature such as the
Balanced Spanning Tree Problem studied by Camerini, Maffioli, Martello, and
Toth [2], by Longshu Wu [12] and by Ficker, Spieksma, and Woeginger [6] or the
Balanced Assignment Problem by Martello, Pulleyblank, Toth, and de Werra [13].
Duin and Volgenant [3] proposed a generic scheme for minimum deviation
problems, that is also usable for solving certain balanced optimization
problems including both the above ones. Ahuja proposed a parametric simplex
method for the general Balanced Linear Programming Problem [1].

The Balanced Network Flow Problem introduced by Scutellà [16] aims to find a
feasible network flow minimizing the difference between the maximum and
minimum flow values along the edges, i.e. $\max_{e\in A}f(e)-\min_{e\in
A}f(e)$. Scutellà presented an algorithm using Newton’s approach that performs
$\mathcal{O}(n^{2}\log^{3}(n))$ max-flow computations, where $n$ is the number
of nodes. The weighted version of the problem has also been solved by Scutellà
and Klinz [11].

This paper examines an extension of the problem above to submodular flows,
where the goal is to find a feasible submodular flow minimizing the difference
between flow values along the edges. A strongly polynomial algorithm is given
for solving the Balanced Submodular Flow Problem with $\mathcal{O}(m^{2})$
submodular function minimizations, where $m$ is the number of edges in the
input graph. Then, Section 4 examines the Weighted Balanced Submodular Flow
problem, that is the problem of finding a feasible submodular flow minimizing
the difference between the maximum and minimum weighted flow values along the
edges. We show that an optimal solution can be found by solving
$\mathcal{O}(n^{4}m^{6}\log^{6}(m))$ submodular function minimization
problems. In Section 5, the Balanced Integral Submodular Flow Problem is
introduced and an optimal integral solution is determined using the fractional
optimum.

##  2 Preliminaries

######  Definition 2.1.

For an underlying set $V$, let ${\cal{}P}(V)$ denote the power set of $V$, i.
e. the set of all subsets of $V$. The set functions
$b,p:{\cal{}P}(V)\to\mathbb{R}$ are called _submodular_ or _supermodular_ if

$b(X)+b(Y)\geq b(X\cup Y)+b(X\cap Y)$ (1)

or

$p(X)+p(Y)\leq p(X\cup Y)+p(X\cap Y)$ (2)

holds for each subsets $X,Y\subseteq V$, respectively. A function is called
_modular_ if it is both sub- and supermodular.

######  Theorem 2.2 (Orlin [14]).

Assuming that the value of a submodular function $b$ can be computed for any
$X\subseteq V$ in time $T$, then the value of $\min\\{b(X):X\subseteq V\\}$
can be computed in time $\mathcal{O}(n^{5}T+n^{6})$.

Whenever a submodular function minimization is used as a subroutine, its
running time will be denoted by $\Upsilon$ for the sake on simplicity.

######  Definition 2.3.

For a directed graph $G=(V,A)$ and a subset of vertices $X\subseteq V$, let
$\tilde{\varrho}(X)$ and $\tilde{\delta}(X)$ denote the set of edges entering
$X$ and leaving $X$, respectively. For a vector $x\in\mathbb{R}^{A}$, let

$\varrho_{x}(X):=\sum_{e\in\tilde{\varrho}(X)}x(e),\quad\delta_{x}(X):=\sum_{e\in\tilde{\delta}(X)}x(e)\quad\mbox{and}\quad\partial_{x}(X):=\varrho_{x}(X)-\delta_{x}(X).$
(3)

Furthermore, let $\varrho(X)$, $\delta(X)$ and $\partial(X)$ denote the number
of edges entering $X$, leaving $X$, and their difference, respectively.

It is straightforward to check that $\varrho_{x}(X)$ and $\delta_{x}(X)$ are
submodular functions for any nonnegative vector $x$. If $l,u\in\mathbb{R}^{A}$
and $l\leq u$, then $\varrho_{u}(X)-\delta_{l}(X)$ is submodular and
$\varrho_{l}(X)-\delta_{u}(X)$ is supermodular.

######  Definition 2.4.

Let us given a directed graph $G=(V,A)$ and a submodular function
$b:{\cal{}P}(V)\to\mathbb{R}$. A vector $x\in\mathbb{R}^{A}$ is called a
_submodular flow_ if

$\varrho_{x}(X)-\delta_{x}(X)\leq b(X)$ (4)

holds for each $X\subseteq V$.

For vectors $l,u\in\mathbb{R}^{A}$, a submodular flow $x$ is called _$(l,u)$
-bounded_ if $l\leq x\leq u$.

######  Theorem 2.5.

For lower and upper bounds $l,u\in\mathbb{R}^{A}$, there exists an
$(l,u)$-bounded submodular flow if and only if $l\leq u$ and

$\varrho_{l}(X)-\delta_{u}(X)\leq b(X)$ (5)

holds for each $X\subseteq V$.

######  Theorem 2.6 (Frank [7]).

Assume that $b:{\cal{}P}(V)\to\mathbb{R}$ is submodular and the value of
$b(X)$ can be computed in time $T$ for any $X\subseteq V$, then an
$(l,u)$-bounded submodular flow — or a set $X$ violating (5) if such a flow
does not exist — can be found in time $\mathcal{O}(n^{5}T)$.

For estimating the running time of the proposed algorithms, we will also use
the following known results.

######  Lemma 2.7 (Goemans [15]).

Let $b\in\mathbb{R}^{p}$ be a real vector and let
$x_{1},x_{2},\dots,x_{q}\in{\\{-1,0,+1\\}}^{p}$ be vectors such that

$0<bx_{i+1}\leq\frac{1}{2}bx_{i}\quad\forall i\in\\{1,2,\dots,q-1\\}$

Then $q=\mathcal{O}(p\log(p))$

######  Theorem 2.8 (Erdős–Szekeres [5]).

Given integer numbers $r,s$ and a sequence of distinct real numbers with
length at least $(r-1)(s-1)+1$, there exists a monotonically increasing
subsequence of length $r$ or a monotonically decreasing subsequence of length
$s$.

In the case when $r=s$, every sequence of length $n$ contains a monotonically
increasing or decreasing subsequence of length $\sqrt{n}$.

######  Theorem 2.9 (Goemans, Gupta and Jaillet [8]).

Let $b$ be a submodular function on $V$, $|V|=n$ and assume that
$b(\emptyset)\geq 0$. Then the value of

$\delta^{*}:=\min\left\\{\delta\geq 0:\min_{S\subseteq V}\left(b(S)+\delta
a(S)\right)\geq 0\right\\}$ (6)

can be computed by performing $\mathcal{O}(n\log^{2}n)$ submodular function
minimization over the set $V$, i. e. in time $\mathcal{O}(n^{2}\Upsilon)$.

A family $R\subseteq{\cal{}P}(V)$ is called a ring family if it is closed
under taking unions and intersections. For a given family of subsets
$X_{1},X_{2},\dots,X_{k}$ of $V$, let $R(X_{1},X_{2},\dots X_{k})$ denote the
ring family generated by $X_{1},X_{2},\dots,X_{k}$.

######  Lemma 2.10 (Goemans et al. [8]).

Let $b:{\cal{}P}(V)\rightarrow\mathbb{R}$ be a submodular function with
$b_{\min}=\min_{S\subseteq V}b(S)\leq 0$. Consider a sequence of distinct sets
$X_{1},X_{2},\dots,X_{q}$ such that $b(X_{1})=b_{\min},b(X_{2})>-2b_{\min}$,
and $b(X_{i})\geq 4b(X_{i-1})$ for $3\leq i\leq q$. Then

$b(X_{q})>\max\\{b(X):X\in R({X_{1},\dots,X_{q-1}})\\},$

therefore $X_{q}\notin R({X_{1},\dots,X_{q-1}})$.

######  Lemma 2.11 (Goemans et al. [8]).

Let $b:{\cal{}P}(V)\rightarrow\mathbb{R}$ be a submodular function and
$\mathcal{T}\subseteq{\cal{}P}(V)$, where $|V|=n$. Assume that $b(S)\leq M$
for all $S\in\mathcal{T}$. Let $X\subseteq V$ be a subset, such that

$b(X)>\frac{n^{2}}{4}(M-b_{\min})$

Then $X\notin R(\mathcal{T})$.

######  Lemma 2.12 (Goemans et al. [8]).

Given a sequence of subsets $X_{1},X_{2}\dots X_{k}$ of $V$, define
$L_{i}=R({X_{1},\dots,X_{i}})$ for $1\leq i\leq k$, where $|V|=n$. Assume that
$X_{i}\notin L_{i-1}$ for all $i>1$. Then

$k\leq\binom{n+1}{2}+1$

######  Theorem 2.13 (Goemans et al. [8]).

Let $b:{\cal{}P}(V)\rightarrow\mathbb{R}$ be a submodular function with
$b_{\min}:=\min_{S\subseteq V}b(S)\leq 0$. Consider a sequence of distinct
sets $T_{1},T_{2},\dots,T_{q}$ such that $f(T_{1})=b_{\min}$,
$b(T_{2})>-2b_{\min}$ and $b(T_{i})\geq 4b(T_{i-1})$ for $3\leq i\leq q$. Then
$q\leq\binom{n+1}{2}+1$.

##  3 Balanced Submodular Flows

######  Definition 3.1.

The _spread_ 111This expression can be seen under another name in the
literature.. of a vector $x\in\mathbb{R}^{A}$ is the value

$\sigma(x):=\max_{a\in A}x(a)-\min_{a\in A}x(a)$

.

The _Balanced Submodular Flow Problem_ is to find a submodular flow of minimum
spread.

######  Problem 3.2.

Let us given a directed graph $G=(V,A)$ and a submodular function
$b:{\cal{}P}(V)\to\mathbb{Z}$. Find

$\sigma^{*}:=\min\left\\{\sigma(x):x\in\mathbb{R}^{A}\quad\varrho_{x}(X)-\delta_{x}(X)\leq
b(X)\quad\forall X\subseteq V\right\\}$ (7)

along with a minimizing vector $x^{*}$.

For the sake of simplicity, we assume that there is no isolated vertex in the
graph $G$ and there exists an unbounded submodular flow, i.e. $b(U)\geq 0$
holds for every subset $U\subseteq V$ with $\varrho(U)=0$ and $\delta(U)=0$.

The following section presents a dual characterization of the value of the
minimum spread and then strongly polynomial algorithms to compute this value
will be given. For technical reasons, the cases of Eulerian and non-Eulerian
graphs are treated separately.

###  3.1 Eulerian Graphs

Throughout this section, a graph $G$ is called _Eulerian_ if $\partial({v})=0$
holds for all $v\in V$. Note that $G$ is not required to be connected.

Clearly, if $G$ is Eulerian and $x\in\mathbb{R}^{A}$ is a submodular flow,
then $x+\alpha\mathbbm{1}$ is also a submodular flow for any
$\alpha\in\mathbb{R}$. Therefore the Balanced Submodular Flow Problem reduces
to the problem of finding the minimum value $\sigma^{*}$ for which there
exists a bounded submodular flow $0\leq x^{*}\leq\sigma^{*}\mathbbm{1}$.
Applying Theorem 2.5, $\sigma^{*}$ is the smallest nonnegative value for which
$b(X)+\sigma^{*}\delta(X)\geq 0$ holds for all $X\subseteq V$. In other words,
we are looking for the root of the function

$f(\sigma):=\min\\{b(X)+\sigma\delta(X):X\subseteq V\\}$ (8)

or $f(\sigma)=0$ if this minimum is negative. This immediately gives the
following dual characterization of the minimum spread submodular flows.

######  Theorem 3.3.

Assume that $G$ is Eulerian. Then

$\sigma^{*}=\max\left\\{\frac{-b(X)}{\delta(X)}:X\subseteq
V,\delta(X)>0\right\\}$ (9)

or $\sigma^{*}=0$ if the value of this maximum is negative.

Therefore, the problem reduces to a fractional optimization problem, the
optimum of which can be calculated using the standard Discrete Newton Method
[15] outlined in Algorithm 1. It is straightforward to see that
$\delta(X_{i})$ strictly decreases in every iteration and a standard argument
shows that the final set $X_{i}$ indeed maximizes the value
$\frac{-b(X)}{\delta(X)}$. Thus we get the following

######  Theorem 3.4.

The value $\sigma^{*}$ of the minimum spread and the corresponding dual $X$ in
Theorem 3.3 are determined by Algorithm 1 within $\mathcal{O}(m)$ iterations.
$\square$

1: Let $\sigma_{1}:=0$.

2: $i:=1$

3:repeat

4: Let $X_{i}:=\operatorname*{arg\,min}\\{b(X)+\sigma_{i}\delta(X):X\subseteq
V\\}$

5: if $b(X_{i})+\sigma_{i}\delta(X_{i})\geq 0$ then

6: RETURN $\sigma_{i},X_{i}$

7: else if $\delta(X_{i})=0$ then

8: RETURN “INFEASIBLE”

9: else

10: $\sigma_{i+1}:=\frac{-b(X_{i})}{\delta(X_{i})}$

11: $i\longleftarrow i+1$

Algorithm 1 Minimum spread calculation in Eulerian graphs

###  3.2 Non-Eulerian Graphs

Now, let us consider the Balanced Submodular Flow Problem in non-Eulerian
graphs. Let $G=(V,A)$ be a directed graph assuming that there exists a node
$v\in V$ such that $\partial({v})\neq 0$. First, we analyze a simpler
algorithm and then improve this algorithm. Furthermore, a dual
characterization of the minimum spread submodular flows is also given. More
precisely, the following theorem will be proved.

######  Theorem 3.5.

Assume that $G$ is not Eulerian. Then

$\sigma^{*}=\max_{X,Y\subseteq V}\left\\{\sigma(X,Y):\partial(X)\geq
0,\partial(Y)<0,\varrho(X)+\delta(X)>0\right\\},$ (10)

where

$\sigma(X,Y):=\frac{b(X)\partial(Y)-b(Y)\partial(X)}{\delta(Y)\partial(X)-\delta(X)\partial(Y)}$
(11)

or $\sigma^{*}=0$ if the value of this maximum is negative.

Note that the condition $\varrho(X)+\delta(X)>0$ in (10) is equivalent to
$\delta(Y)\partial(X)-\delta(X)\partial(Y)\neq 0$, assuming that
$\partial(X)\geq 0,\partial(Y)<0$ hold for $X,Y$. Therefore, the expression in
(10) is well-defined.

In order to prove Theorem 3.5, we first show that the expression above
constitutes a lower bound of $\sigma^{*}$ for any pairs of sets $X$ and $Y$.

######  Lemma 3.6.

Let $X,Y\subseteq V$ such that $\partial(X)\geq 0$, $\partial(Y)<0$ and
$\varrho(X)+\delta(X)>0$. Then

$\sigma^{*}\geq\sigma(X,Y).$ (12)

###### Proof.

By the definition of $x^{*}$, there exists a real value $\kappa$ such that
$\kappa\mathbbm{1}\leq x^{*}\leq(\kappa+\sigma^{*})\mathbbm{1}$. Using Theorem
2.5 with $l:=\kappa\mathbbm{1}$ and $u:=(\kappa+\sigma^{*})\mathbbm{1}$ we get

$\kappa\partial(X)-\sigma^{*}\delta(X)\leq b(X)$ (13)

and

$\kappa\partial(Y)-\sigma^{*}\delta(Y)\leq b(Y).$ (14)

From these, we get

$b(X)\partial(Y)+\sigma^{*}\delta(X)\partial(Y)\leq\kappa\partial(X)\partial(Y)\leq
b(Y)\partial(X)+\sigma^{*}\delta(Y)\partial(X),$ (15)

therefore

$\sigma^{*}\big{(}\delta(Y)\partial(X)-\delta(X)\partial(Y)\big{)}\geq
b(X)\partial(Y)-b(Y)\partial(X).$ (16)

Since $\delta(Y)\partial(X)-\delta(X)\partial(Y)>0$, the equation above is
equivalent to

$\sigma^{*}\geq\frac{b(X)\partial(Y)-b(Y)\partial(X)}{\delta(Y)\partial(X)-\delta(X)\partial(Y)}=\sigma(X,Y).$
(17)

∎

###### Proof of Theorem 3.5.

Let

$\displaystyle\kappa(X,Y):=\frac{b(X)\delta(Y)-b(Y)\delta(X)}{\delta(Y)\partial(X)-\delta(X)\partial(Y)}$
(18)

and let $X$ and $Y$ be a pair of sets maximizing $(\ref{eq:eqxy})$ and among
them the one maximizing $\kappa^{*}=\displaystyle\kappa(X,Y)$. We show that
there exists a bounded submodular flow such that $\kappa^{*}\mathbbm{1}\leq
x\leq(\kappa^{*}+\sigma^{*})\mathbbm{1}$.

Suppose to the contrary, assume that such a flow does not exist. Then, Theorem
2.5 states that a set $C\subseteq V$ with the property

$\kappa^{*}\partial(C)-\sigma^{*}\delta(C)>b(C)$

must exist. Note that $\varrho(X)+\delta(X)>0$, since otherwise
$\kappa(X,Y)=0$ and therefore $b(C)<0$ would hold, thus the problem would be
infeasible.

If $\partial(C)<0$ and $\partial(X)>0$, we get

$\displaystyle\big{(}b(X)\partial(Y)-b(Y)\partial(X)\big{)}\big{(}\delta(C)\partial(X)-\delta(X)\partial(C)\big{)}$
$\displaystyle=\quad$ $\displaystyle
b(X)\partial(Y)\delta(C)\partial(X)-b(X)\partial(Y)\delta(X)\partial(C)-$
$\displaystyle
b(Y)\partial(X)\delta(C)\partial(X)+b(Y)\partial(X)\delta(X)\partial(C)$
$\displaystyle=\quad$
$\displaystyle-b(X)\partial(Y)\delta(X)\partial(C)+\partial(X)\big{(}b(X)\partial(Y)\delta(C)-$
$\displaystyle b(Y)\delta(C)\partial(X)+b(Y)\delta(X)\partial(C)\big{)}$
$\displaystyle=\quad$
$\displaystyle-b(X)\partial(Y)\delta(X)\partial(C)+\partial(X)\big{(}\delta(C)\big{(}b(X)\partial(Y)-$
$\displaystyle
b(Y)\partial(X)\big{)}+\partial(C)\big{(}b(Y)\delta(X)\big{)}\big{)}$
$\displaystyle=\quad$
$\displaystyle\partial(X)\big{(}\delta(C)\big{(}b(X)\partial(Y)-b(Y)\partial(X)\big{)}-\partial(C)\big{(}b(X)\delta(Y)-b(Y)\delta(X)\big{)}\big{)}$
$\displaystyle-b(X)\partial(Y)\delta(X)\partial(C)+\partial(X)\partial(C)b(X)\delta(Y)$
$\displaystyle=\quad$
$\displaystyle\big{(}\delta(Y)\partial(X)-\delta(X)\partial(Y)\big{)}\partial(X)\big{(}\delta(C)\sigma-\partial(C)\kappa\big{)}-$
$\displaystyle
b(X)\partial(Y)\delta(X)\partial(C)+\partial(X)\partial(C)b(X)\delta(Y)$
$\displaystyle<\quad$
$\displaystyle\big{(}\delta(Y)\partial(X)-\delta(X)\partial(Y)\big{)}\partial(X)(-b(C))$
$\displaystyle-b(X)\partial(Y)\delta(X)\partial(C)+\partial(X)\partial(C)b(X)\delta(Y)$
$\displaystyle=\quad$
$\displaystyle\big{(}\delta(Y)\partial(X)-\delta(X)\partial(Y)\big{)}\big{(}b(X)\partial(C)-\partial(X)b(C)\big{)},$

therefore

$\sigma(X,Y)<\sigma(X,C),$

contradicting the maximizing property of $X$ and $Y$.

By the same token, if $\partial(C)\geq 0$ we get that

$\sigma(X,Y)<\sigma(C,Y).$

Finally, if $\partial(C)<0$ and $\partial(X)=0$, we get

$\kappa(X,Y)<\kappa(X,C)$

in the same way, which finishes the proof. ∎

###  3.3 Algorithm for non-Eulerian Graphs

1: Choose $X_{1},Y_{1}\subseteq V$ such that $\partial(X_{1})\geq 0$ and
$\partial(Y_{1})<0$.

2: $i:=1$

3:repeat

4: $\displaystyle\sigma_{i}:=\sigma(X_{i},Y_{i})$

5: $\displaystyle\kappa_{i}:=\kappa(X_{i},Y_{i})$

6:
$C_{i}\in\operatorname*{arg\,min}\\{b(X)+\sigma_{i}\delta(X)-\kappa_{i}\partial(X):X\subseteq
V\\}$

7: if $b(C_{i})+\sigma_{i}\delta(C_{i})-\kappa_{i}\partial(C_{i})\geq 0$ then

8: RETURN $\kappa_{i},\sigma_{i},X_{i},Y_{i}$

9: else if $\varrho(C_{i})+\delta(C_{i})=0$ then

10: RETURN “INFEASIBE”

11: else if $\partial(C_{i})\geq 0$ then

12: $X_{i+1}:=C_{i}$

13: $Y_{i+1}:=Y_{i}$

14: else

15: $X_{i+1}:=X_{i}$

16: $Y_{i+1}:=C_{i}$

17: $i\longleftarrow i+1$

Algorithm 2 Minimum spread calculation in non-Eulerian graphs

The proof of Theorem 3.5, immediately provides the algorithm outlined in
Algorithm 2 for finding an optimal pair of sets $X$ and $Y$.

The initial sets $X_{1}$ and $Y_{1}$ can be chosen as single node sets
satisfying conditions in line 1.

Computing $C_{i}$ in line 6 involves in the minimization of the submodular
function $b(X)+\sigma_{i}\delta(X)-\kappa_{i}\partial(X)$. If the algorithm
terminates at line 8, then the last value of the $\sigma_{i}$ is optimal and
$X_{i},Y_{i}$ are maximizing sets in Theorem 3.5.

Note, that $\partial(X_{i})\geq 0$ and $\partial(Y_{i})<0$ hold in every
iteration, therefore the denominator of $\sigma_{i}$ and $\kappa_{i}$ are not
zero.

The algorithm is clearly finite because the value $\sigma_{i}$ is
monotonically increasing throughout the execution, and either the value of
$\sigma_{i}$ or $\kappa_{i}$ strictly increases in each iteration.

In the following, we will show that not only is Algorithm 2 finite, but in
fact it runs in strongly polynomial time. Let us consider two sets
$Z_{1},Z_{2}\subseteq V$ _equivalent_ if $\delta(Z_{1})=\delta(Z_{2})$,
$\varrho(Z_{1})=\varrho(Z_{2})$ and $b(Z_{1})=b(Z_{2})$.

######  Lemma 3.7.

The algorithm computes at most ${(m+1)}^{2}$ non-equivalent sets.

###### Proof.

The lemma is proved by showing that if $C_{1}$ and $C_{2}$ are non-equivalent
sets found by the algorithm and $\delta(C_{1})=\delta(C_{2})$ then
$\varrho(C_{1})\neq\varrho(C_{2})$.

If $b(C_{1})=b(C_{2})$, then $\varrho(Z_{1})\neq\varrho(Z_{2})$, because they
are non-equivalent. Therefore, we may assume that $b(C_{1})\neq b(C_{2})$.

First, let us consider the case when $\delta(C_{1})=\delta(C_{2})=0$. Then
$\varrho(C_{1})\neq 0$ and $\varrho(C_{2})\neq 0$, otherwise the problem would
be infeasible. Thus, the expression in line 6 can be rewritten as

$\operatorname*{arg\,min}\\{b(X)+\sigma_{i}\delta(X)-\kappa_{i}\partial(X)\\}=\operatorname*{arg\,min}\bigg{\\{}\varrho(x)\left(\frac{b(X)}{\varrho(X)}-\kappa_{i}\right)\bigg{\\}}.$
(19)

By re-indexing we may assume that
$\frac{b(C_{1})}{\varrho(C_{1})}>\frac{b(C_{2})}{\varrho(C_{2})}$. (If these
two values are equal then the algorithm will only find the set with the
greater $\varrho$ value.) Since $C_{1}$ minimizes the right hand side of (19)
for $\kappa_{1}$, we have $\varrho(C_{i_{1}})<\varrho(C_{i_{2}})$.

Now assume that $\delta(C_{1})=\delta(C_{2})>0$ and $b(C_{1})>b(C_{2})$. Then
the expression in line 6 can be rewritten as

$\operatorname*{arg\,min}\\{b(X)+\sigma_{1}\delta(X)-\kappa_{1}\partial(X)\\}=\operatorname*{arg\,max}\bigg{\\{}\delta(x)\left(\frac{\kappa_{1}\partial(X)-b(X)}{\delta(X)}-\sigma_{1}\right)\bigg{\\}}.$
(20)

Since $\delta(C_{1})=\delta(C_{2})$ and $C_{1}$ maximizes the right hand side
of (20) for $\kappa_{1},\sigma_{1}$, then

$\frac{\kappa_{1}\partial(C_{1})-b(C_{1})}{\delta(C_{1})}\geq\frac{\kappa_{1}\partial(C_{2})-b(C_{2})}{\delta(C_{2})},$

from which we get that
$\frac{\partial(C_{1})}{\delta(C_{1})}>\frac{\partial(C_{2})}{\delta(C_{2})}$.
Thus $\varrho(C_{1})\neq\varrho(C_{2})$, which finishes the proof. ∎

######  Lemma 3.8.

Assume that $X_{i}$ and $X_{j}$ are equivalent for some $i\neq j$. Then
$Y_{i}$ and $Y_{j}$ are not equivalent.

###### Proof.

If $X_{i}$ is equivalent to $X_{j}$ and $Y_{i}$ is equivalent to $Y_{j}$, then
$\sigma_{i}=\sigma_{j}$ and $\kappa_{i}=\kappa_{j}$ hold. But — as we have
seen in the proof of Theorem 3.5 — the $\sigma_{i}$ is monotonically
increasing, and either $\sigma_{i}$ or $\kappa_{i}$ strictly increases at each
iteration. ∎

Combining Lemma 3.7 and 3.8, we immediately get the following upper bound on
the number of iterations.

######  Theorem 3.9.

Algorithm 2 terminates after at most $\mathcal{O}(m^{4})$ iterations.
$\square$

The running time of each single iteration is dominated by the submodular
function minimization, therefore we get the following.

######  Theorem 3.10.

Algorithm 2 computes $\sigma^{*}$ along with the maximizing sets $X$ and $Y$
in $\mathcal{O}(m^{4}\Upsilon)$ time. $\square$

###  3.4 Improved Algorithm for Non-Eulerian Graphs

This section presents an $\mathcal{O}(m^{2}\Upsilon)$ time algorithm for
finding the minimum spread and the corresponding dual pair of sets $X$ and
$Y$.

1:Choose $X_{1},Y_{1}\subseteq V$ such that $\partial(X_{1})\geq 0$ and
$\partial(Y_{1})<0$

2:$i:=1,\quad j:=1$

3:repeat

4: $\sigma_{i}:=\sigma(X_{i},Y_{j})$

5: $\kappa_{i}:=\kappa(X_{i},Y_{j})$

6:
$C\in\operatorname*{arg\,min}\\{b(X)+\sigma\delta(X)-\kappa\partial(X):X\subseteq
V\\}$

7: if $b(C)+\sigma_{i}\delta(C)-\kappa_{i}\partial(C)\geq 0$ then

8: RETURN $\kappa_{i},\sigma_{i},X_{i},Y_{j}$

9: else if $\varrho(C)+\delta(C)=0$ then

10: RETURN “INFEASIBLE”

11: else if $\delta(C)=0$ then

12: $X_{1}=C$ and $i:=1$

13: while $\sigma(C,Y_{j})\leq\sigma(C,Y_{j-1})$ do

14: $j:=j-1$

15: else

16: while $\delta(X_{i})=0$ or
$\frac{\partial(X_{i})}{\delta(X_{i})}\leq\frac{\partial(C)}{\delta(C)}$ or
$\kappa(C,X_{i})\geq\kappa(C,X_{i-1})$ do

17: $i:=i-1$

18: while
$\frac{\partial(Y_{J})}{\delta(Y_{j})}\geq\frac{\partial(C)}{\delta(C)}$ or
$\kappa(C,Y_{j})\leq\kappa(C,Y_{j-1})$ do

19: $j:=j-1$

20: if $\partial(C)\geq 0$ then

21: $X_{i+1}:=C$

22: $i:=i+1$

23: else

24: $Y_{j+1}:=C$

25: $j:=j+1$

Algorithm 3 Minimum spread calculation

The improved procedure is outlined in Algorithm 3. The main difference
compared to Algorithm 2 is that the algorithm revisits the previously found
sets at each iteration, ensuring that every set can be found at most once.
Therefore, the number of iterations is equal to the number of non-equivalent
sets found by the algorithm.

For this we maintain sequences of previously calculated sets
$X_{1},X_{2},\dots,X_{i}$ and $Y_{1},Y_{2},\dots,Y_{j}$ such that

$\frac{\partial(Y_{1})}{\delta(Y_{1})}<\frac{\partial(Y_{2})}{\delta(Y_{2})}<\dots<\frac{\partial(Y_{j})}{\delta(Y_{j})}<\frac{\partial(X_{i})}{\delta(X_{i})}<\dots<\frac{\partial(X_{2})}{\delta(X_{2})}<\frac{\partial(X_{1})}{\delta(X_{1})}$
(21)

At each iteration, the unnecessary sets are deleted. Note that — by Theorem
2.5— if there exists a set $Z$ with $\delta(Z)=0$ and $\varrho(Z)\neq 0$ and
$\kappa>\frac{b(Z)}{\varrho(Z)}$, then there exists no feasible submodular
flow with lower bound $\kappa\mathbbm{1}$. Analogously, if $\delta(Z)>0$ and
$\sigma<\frac{\kappa\partial(Z)-b(Z)}{\delta(Z)}$, then a
$(\kappa\mathbbm{1},(\kappa+\sigma)\mathbbm{1})$-bounded submodular flow
cannot exist. Therefore, if the value of a flow is at least $\kappa$ on each
edge, then spread of the flow is at least
$\frac{\kappa\partial(Z)-b(Z)}{\delta(Z)}$.

Therefore a set $X_{i}$ is to be considered unnecessary if for any
$\kappa^{\prime}$ there exists a set
$Z\in\\{Y_{1},Y_{2},\dots,Y_{j},X_{i-1},\dots,X_{1}\\}$ such that

$\frac{\kappa^{\prime}\partial(X_{i})-b(X_{i})}{\delta(X_{i})}\leq\frac{\kappa^{\prime}\partial(Z)-b(Z)}{\delta(Z)}.$

It means that for any $\kappa^{\prime}$, there exists another found set $Z$
which defines a larger lower bound for the spread than those obtained by
$X_{i}$. Due to the deleting process at the end of every iteration, the
inequalities in (21) hold true.

It is clear that if
$Z,Z^{\prime}\in\\{Y_{1},Y_{2},\dots,Y_{j},X_{i},X_{i-1},\dots,X_{1}\\}$ are
two different sets and
$\frac{\partial(Z)}{\delta(Z)}<\frac{\partial(Z^{\prime})}{\delta(Z^{\prime})}$
then the followings holds true.

$\displaystyle\frac{\kappa^{\prime}\partial(Z)-b(Z)}{\delta(Z)}<\frac{\kappa^{\prime}\partial(Z^{\prime})-b(Z^{\prime})}{\delta(Z^{\prime})}\quad\text{if
}\kappa^{\prime}<\kappa(Z,Z^{\prime})$
$\displaystyle\frac{\kappa^{\prime}\partial(Z)-b(Z)}{\delta(Z)}=\frac{\kappa^{\prime}\partial(Z^{\prime})-b(Z^{\prime})}{\delta(Z^{\prime})}\quad\text{if
}\kappa^{\prime}=\kappa(Z,Z^{\prime})$
$\displaystyle\frac{\kappa^{\prime}\partial(Z)-b(Z)}{\delta(Z)}>\frac{\kappa^{\prime}\partial(Z^{\prime})-b(Z^{\prime})}{\delta(Z^{\prime})}\quad\text{if
}\kappa^{\prime}>\kappa(Z,Z^{\prime})$

At the beginning of iteration $i$, every set in
$\\{Y_{1},Y_{2},\dots,Y_{j},X_{i},X_{i-1},\dots,X_{1}\\}$ was necessary, thus

$\kappa(Y_{1},Y_{2})<\kappa(Y_{2},Y_{3})<\cdots<\kappa(Y_{j},X_{j})<\cdots<\kappa(X_{2},X_{1}).$

Therefore, the following properties hold true in every iteration.

  1. 1.

If $\kappa<\kappa(Y_{1},Y_{2})$ and
$Z\in\\{Y_{2},\dots,Y_{j},X_{i},X_{i-1},\dots,X_{1}\\}$, then

$\frac{\kappa\partial(Y_{1})-b(Y_{1})}{\delta(Y_{1})}>\frac{\kappa\partial(Z)-b(Z)}{\delta(Z)}.$

  2. 2.

If
$\kappa(Y_{j^{\prime}-1},Y_{j^{\prime}})<\kappa<\kappa(Y_{j^{\prime}},Y_{j^{\prime}+1})$
and $Z\in\\{Y_{1},Y_{2},\dots,Y_{j},X_{i},X_{i-1},\dots,X_{1}\\}$, $Z\neq
Y_{j^{\prime}}$, then

$\frac{\kappa\partial(Y_{j^{\prime}})-b(Y_{j^{\prime}})}{\delta(Y_{j^{\prime}})}>\frac{\kappa\partial(Z)-b(Z)}{\delta(Z)}.$

  3. 3.

If $\kappa(Y_{j-1},Y_{j})<\kappa<\kappa(Y_{j},X_{i})$ and
$Z\in\\{Y_{1},Y_{2},\dots Y_{j-1},X_{i},X_{i-1},\dots,X_{1}\\}$, then

$\frac{\kappa\partial(Y_{j})-b(Y_{j})}{\delta(Y_{j})}>\frac{\kappa\partial(Z)-b(Z)}{\delta(Z)}.$

Similar properties hold for any
$X_{i^{\prime}}\in\\{X_{i},X_{i-1},\dots,X_{1}\\}$.

If $\delta(C)=0$, then $\kappa_{i}>\frac{b(C)}{\varrho(C)}$. In this case
(line (11)) every set in $\\{X_{i},X_{i-1}\dots X_{1}\\}$ is unnecessary. At
the beginning of this iteration, $Y_{j^{\prime}}$ defines the largest lower
bound for the spread if and only if
$\kappa(Y_{j^{\prime}-1},Y_{j^{\prime}})\leq\kappa\leq\kappa(Y_{j^{\prime}},Y_{j^{\prime}+1})$.
Therefore, $Y_{j^{\prime}}$ is no longer necessary if and only if
$\frac{b(C)}{\varrho(C)}<\kappa(Y_{j^{\prime}-1},Y_{j^{\prime}})$. This is
equivalent to the condition $\sigma(C,Y_{j})\leq\sigma(C,Y_{j-1})$.

If $\delta(C)\neq 0$, we have that

$\frac{\kappa\partial(Y_{j})-b(Y_{j})}{\delta(Y_{j})}=\sigma(X_{i},Y_{j})<\frac{\kappa\partial(C)-b(C)}{\delta(C)}.$

Therefore, $X_{i}$ or $Y_{j}$ are unnecessary whenever
$\frac{\partial(X_{i})}{\delta(X_{i})}\leq\frac{\partial(C)}{\delta(C)}$ or
$\frac{\partial(Y_{j})}{\delta(Y_{j})}\geq\frac{\partial(C)}{\delta(C)}$ hold,
respectively. Since $X_{i}$ was necessary at the end of the previous
iteration, then

$\frac{\kappa\partial(X_{i})-b(X_{i})}{\delta(X_{i})}\geq\frac{\kappa\partial(X)-b(X)}{\delta(X)}\quad\forall
X\in\\{X_{i-1},\dots,X_{1}\\},$

holds for any $\kappa(Y_{j},X_{i})\leq\kappa\leq\kappa(X_{i},X_{i-1})$, which
means that $X_{i}$ is unnecessary if and only if

$\frac{\kappa\partial(X_{i})-b(X_{i})}{\delta(X_{i})}\leq\frac{\kappa\partial(C)-b(C)}{\delta(C)}\quad\forall\kappa\in[\kappa(Y_{j},X_{i}),\kappa(X_{i},X_{i-1})]$
(22)

Since $\frac{\partial(X_{i})}{\delta(X_{i})}>\frac{\partial(C)}{\delta(C)}$
(otherwise $X_{i}$ would have already been deleted), it is enough to check if
expression (22) holds at the end of the interval, i. e. for
$\kappa=\kappa(X_{i},X_{i-1})$. Thus, inequality (22) reduces to
$\kappa(C,X_{i})\geq\kappa(C,X_{i+1})$. The decision of whether or not $Y_{j}$
is necessary can be made in the same way. Note that if
$\frac{\partial(X_{1})}{\delta(X_{1})}>\frac{\partial(C)}{\delta(C)}$, then
$X_{1}$ will not be deleted. Analogously, if
$\frac{\partial(Y_{1})}{\delta(Y_{1})}<\frac{\partial(C)}{\delta(C)}$, then
$Y_{1}$ will not be deleted in the current iteration.

After deleting all the unnecessary sets, the algorithm adds the new set $C$ to
the appropriate subsequence. Note that $C$ is always necessary in the
iteration where it is computed and it is not equivalent to any
$Z\in\\{Y_{1},Y_{2},\dots,Y_{j},X_{i},X_{i-1},\dots,X_{1}\\}$. In addition, a
deleted (i. e. unnecessary) set cannot become necessary again. Therefore, the
algorithm will find every set at most once, and delete it at most once.

To sum up, the algorithm finishes after $\mathcal{O}(m^{2})$ iterations,
therefore we get the following theorem.

######  Theorem 3.11.

Algorithm 3 solves the Balanced Submodular Flow Problem in
$\mathcal{O}(m^{2}\Upsilon)$ time. $\square$

##  4 Weighted Balanced Submodular Flows

This section introduces the weighted version of the problem and extends the
dual characterization to this case. Then, a strongly polynomial algorithm is
presented to determine the minimum weighted spread with a positive weight
function.

######  Definition 4.1.

Given a weight function $c:A\to\mathbb{R}^{+}$ on the edges, the _weighted
spread_ of a vector $x\in\mathbb{R}^{A}$ is the value

$\sigma_{c}(x):=\max_{a\in A}c(a)x(a)-\min_{a\in A}c(a)x(a)$

The _Balanced Submodular Flow Problem_ is defined as the following.

######  Problem 4.2.

Let us given a directed graph $G=(V,A)$, a weight function
$c:A\to\mathbb{R}^{+}$ and a submodular function
$b:{\cal{}P}(V)\to\mathbb{Z}$. Find

$\sigma^{*}:=\min\left\\{\sigma_{c}(x):x\in\mathbb{R}^{A},\varrho_{x}(X)-\delta_{x}(X)\leq
b(X)\quad\forall X\subseteq V\right\\}$ (23)

along with a minimizing vector $x$.

Let us introduce the following notations.

$\displaystyle\tilde{c}(e)$ $\displaystyle:=\frac{1}{c(e)}$
$\displaystyle\varrho_{\tilde{c}}(X)$
$\displaystyle:=\sum_{e\in\varrho(X)}\tilde{c}(e)$
$\displaystyle\delta_{\tilde{c}}(X)$
$\displaystyle:=\sum_{e\in\delta(X)}\tilde{c}(e)$
$\displaystyle\partial_{\tilde{c}}(X)$
$\displaystyle:=\varrho_{\tilde{c}}(X)-\delta_{\tilde{c}}(X)$

######  Definition 4.3.

For an arbitrary real value $\kappa\in\mathbb{R}$, let $s(\kappa)$ denote the
minimal value $\sigma$ for which there exists a
$\left(\kappa\tilde{c},(\kappa+\sigma)\tilde{c}\right)$-bounded submodular
flow $x$.

Clearly,

$\sigma^{*}=\min_{\kappa}s(\kappa)$

The following theorem determines a dual characterization of Problem 4.2 and
then we will show that the optimal spread can be computed in strongly
polynomial time.

######  Theorem 4.4.

Assume that there exists a set $X\subseteq V$ such that
$\partial_{\tilde{c}}(X)\gneqq 0$. Then

$\sigma^{*}=\max\Bigg{\\{}\frac{-b(X)\partial_{\tilde{c}}(Y)+b(Y)\partial_{\tilde{c}}(X)}{\delta_{\tilde{c}}(X)\partial_{\tilde{c}}(Y)-\delta_{\tilde{c}}(Y)\partial_{\tilde{c}}(X)}:\partial_{\tilde{c}}(X)\geq
0,\partial_{\tilde{c}}(Y)<0\Bigg{\\}},$ (24)

or $\sigma^{*}=0$ if the maximum above is negative.

If $\partial_{\tilde{c}}(X)=0$ holds for all $X\subseteq V$, then $s(\kappa)$
is a constant function. In this case

$\sigma^{*}=\max_{\partial_{\tilde{c}}(X)=0}\Bigg{\\{}\frac{-b(X)}{\delta_{\tilde{c}}(C)}:b(X)<0\Bigg{\\}},$
(25)

or $\sigma^{*}=0$ if $b(X)\geq 0$ hold for all $X\subseteq V$.

The proof of Theorem 4.4 follows the same pattern as that of Theorem 3.5 and
the details are left to the reader.

The following two sections present a strongly polynomial algorithm to compute
the value of $s(\kappa)$ then to find its minimum, therefore solving the
weighted version of the Balanced Submodular Flow Problem. This latter
algorithm also provides a corresponding dual solution described in Theorem
4.4.

###  4.1 Computing the Value of $s(\kappa)$

In this section, the following theorem is proved.

######  Theorem 4.5.

The value of $s(\kappa)$ can be computed with
$n^{2}+\mathcal{O}(m\log^{2}(m))$ submodular function minimizations.

By Theorem 2.5, we get that

######  Claim 4.6.

$s(\kappa)=\min\left\\{\sigma\geq 0:\min_{X\subseteq
V}\left(b(S)-\kappa\partial_{\tilde{c}}(X)-\sigma\delta_{\tilde{c}}(X)\right)\geq
0\right\\}$ (26)

$\square$

Note that $b(S)-\kappa\partial_{\tilde{c}}(X)$ is a submodular function,
therefore Theorem 4.5 is clearly a special case of the following extension of
Theorem 2.9 proven below.

######  Theorem 4.7.

Let $b$ be a submodular function over the set $V$, $|V|=n$ and assume that
$b(\emptyset)\geq 0$. In addition, let $f:{\cal{}P}(V)\to{\cal{}P}(A)$ and
$a\in\mathbb{R}^{A}$, such that $b^{\prime}(S)=a(f(S))=\sum_{e\in f(S)}a(e)$
is also submodular and let $|E|=m$. Then the value of

$\delta^{*}:=\min\left\\{\delta\geq 0:\min_{S\subseteq V}\left(b(S)+\delta
a(f(S))\right)\geq 0\right\\}$ (27)

can be computed by performing $n^{2}+\mathcal{O}(m\log^{2}m)$ submodular
function minimization over the set $V$, i. e. in time
$\mathcal{O}((n^{2}+m\log^{2}m)\Upsilon)$.

###### Proof.

Note that $\delta^{*}$ is the smallest root of the piecewise linear concave
function

$h(\delta):=\min_{S\subseteq V}\left(b(S)+\delta a(f(S))\right).$

Therefore $\delta^{*}$ can be computed using the well-known Discrete Newton
Method outlined in Algorithm 4. In the following, we show that the number of
iterations taken by the algorithm is at most $n^{2}+\mathcal{O}(m\log^{2}m)$.

1:$\delta_{1}=0$, $i=0$

2:repeat

3: $i=i+1$

4: $h_{i}=\min\\{b(X)+\delta_{i}a(f(X))\\}$

5: $X_{i}\in\operatorname*{arg\,min}\\{b(X)+\delta_{i}a(f(X))\\}$

6: if $h_{i}=0$ then return $\delta_{i},X_{i}$

7: $a_{i}:=a(f(X_{i}))$

8: if $a_{i}=0$ then return UNDEFINED, $X_{i}$

9: $\delta_{i+1}=\frac{-b(X_{i})}{a_{i}}$

Algorithm 4 Discrete Newton Method

We use the following generic properties of the Discrete Newton Method ([15]).

######  Claim 4.8.

  1. 1.

$h_{1}<h_{2}<\cdots<h_{t}=0$

  2. 2.

$\delta_{1}<\delta_{2}<\dots\delta_{t}$

  3. 3.

$a_{1}>a_{2}>\cdots>a_{t}\geq 0$ $\square$

######  Claim 4.9.

$\frac{h_{i+1}}{h_{i}}+\frac{a_{i+1}}{a_{i}}\leq 1$

$\square$

Let $I$ denote the set of indices for which
$\frac{a_{i+1}}{a_{i}}\leq\frac{2}{3}$. Then — as a direct consequence of
Lemma 2.7 — we get that

$|I|=\Big{|}\left\\{i:\frac{a_{i+1}}{a_{i}}\leq\frac{2}{3}\right\\}\Big{|}=\mathcal{O}(m\log
m).$

Let $J$ be the set of the remaining indices, i. e.

$J=\left\\{i:\frac{a_{i+1}}{s_{i}}>\frac{2}{3}\right\\}.$

Due to Claim 4.9, $\frac{h_{i+1}}{h_{i}}<\frac{1}{3}$ hold for any $i\in J$.

Let us consider the smallest partition $J=J_{1}\cup J_{2},\cup\cdots\cup
J_{q}$ such that $J_{l}$ is an interval for each $l=1,\dots,q$, i. e.
$J_{l}=[s_{l},t_{l}]$ and $t_{l}+1<s_{l+1}$. Let
$t^{\prime}_{l}:=t_{l}-\lceil\log(n^{2}/4)\rceil$ and
$J^{\prime}_{l}:=[s_{l},t^{\prime}_{l}]$. (If $t^{\prime}_{l}<s_{l}$, then let
$J^{\prime}_{l}:=\emptyset$). Let $J^{\prime}:=J^{\prime}_{1}\cup
J^{\prime}_{2},\cup\cdots\cup J^{\prime}_{q}$.

######  Lemma 4.10.

For each $j\in J^{\prime}$, we have

$X_{j}\notin R(X_{k}:k\in J^{\prime},\ j<k).$

###### Proof.

On the one hand, let $s_{i}\leq l<t^{\prime}_{i}$ for some $1\leq i\leq q$.
Then the sequence $X_{l},X_{l+1},\dots,X_{t^{\prime}_{i}}$ with the submodular
function $b^{\prime}(X):=b(X)+\delta_{t_{i}}a(f(X))$ satisfies the conditions
of Lemma 2.10, therefore $X_{l}\notin
R(X_{l+1},X_{l+2},\dots,X_{t^{\prime}_{i}})$.

On the other hand, if $i<q$, then let $F:=J^{\prime}_{i+1}\cup\dots\cup
J^{\prime}_{q}$. Clearly, $b^{\prime}(X_{j})<0$ for each $j\in F$. Lemma 2.11
with $M=0$ implies222Note that
$b^{\prime}(X_{t_{i}})=\min\\{b^{\prime}(X):X\subseteq V\\}$. that
$b^{\prime}(X)\leq-\frac{n^{2}}{4}b^{\prime}(X_{t_{i}})$ holds for each $X\in
R(X_{k}:k\in F)$. Due to Theorem 2.13, $X_{l}\in R(F)$ only if
$t^{\prime}_{i}<l\leq t_{i}$. Therefore if $s_{i}\leq l\leq t^{\prime}_{i}$,
then $X_{l}\notin R(X_{k}:k\in J^{\prime},\quad l<k)$, finishing the proof. ∎

The sequence $(X_{j}:j\in J^{\prime})$ meets the conditions of Lemma 2.12,
thus $|J^{\prime}|\leq\binom{n+1}{2}+1$.

Finally the total number of iterations taken by Algorithm 4 is

$\displaystyle\big{|}I\big{|}+\big{|}J\big{|}$
$\displaystyle\leq\big{|}I\big{|}+\big{|}J^{\prime}\big{|}+2\log(n)|I|$
$\displaystyle\leq O(m\log m)+\binom{n+1}{2}+1+2\log(n)O(m\log m)$
$\displaystyle=O(n^{2}+m\log^{2}m),$

finishing the proof of Theorem 4.5. ∎

Note that when Algorithm 4 is used to compute the value of $s(\kappa_{0})$ by
finding the smallest root of the function $h(\sigma):=\min_{X\subseteq
V}\left(b(S)-\kappa\partial_{\tilde{c}}(X)-\sigma\delta_{\tilde{c}}(X)\right)$,
and the algorithm terminates at line 8, then the provided set $X\subseteq V$
will have the properties $\delta_{\tilde{c}}(X)=0$ and
$\kappa_{0}>\frac{b(X)}{\varrho_{\tilde{c}}(X)}$. Therefore, no submodular
flow with lower bound $\kappa_{0}\tilde{c}$ may exist.

With this information in hand, one can compute the largest value
$\kappa_{\max}$ for which $s(\kappa_{\max})$ is defined (i. e. there exists a
submodular flow with lower bound $\kappa_{\max}\tilde{c}$) as follows.

By Theorem 2.5,

$\kappa_{\max}=\max\bigg{\\{}\kappa:\min\\{b(X)-\kappa\varrho_{\tilde{c}}(X):\forall
X\subseteq V,\quad\delta_{\tilde{c}}(X)=0\\}\geq 0\bigg{\\}}.$

Therefore, this value can again be computed by applying the Discrete Newton
Method to find the largest root of the concave function

$h(\kappa):=\min\\{b(X)-\kappa\varrho_{\tilde{c}}(X):\forall X\subseteq
V,\quad\delta_{\tilde{c}}(X)=0\\}$

with initial value $\kappa_{0}$.

By the same token as in the proof of Theorem 4.5, the value of $\kappa_{\max}$
can be found in $n^{2}+\mathcal{O}(m\log^{2}(m))$ iterations.

###  4.2 Minimizing $s(\kappa)$

######  Claim 4.11.

The function of $s(\kappa)$ is a convex function.

###### Proof.

For any $\kappa_{1},\kappa_{2}\in\mathbb{R}$, let $x_{1}$ and $x_{2}$ be
submodular flows such that $\kappa_{i}\mathbbm{1}\leq
x_{i}\leq(\kappa_{i}+s(\kappa_{i}))\mathbbm{1}$, and let $0\leq\lambda\leq 1$.
Then $x^{\prime}:=\lambda x_{1}+(1-\lambda)x_{2}$ is also a submodular flow
and $[\lambda\kappa_{1}+(1-\lambda)\kappa_{2}]\mathbbm{1}\leq
x^{\prime}\leq[\lambda(\kappa_{1}+s(\kappa_{1}))+(1-\lambda)(\kappa_{2}+s(\kappa_{2}))]\mathbbm{1}$,
therefore

$s(\lambda\kappa_{1}+(1-\lambda)\kappa_{2})\leq\lambda
s(\kappa_{1})+(1-\lambda)s(\kappa_{2}).$ (28)

∎

Since $s(\kappa)$ is a convex function, the Handler–Zang method — detailed in
Appendix A — is applicable to find the minimum of it. It will be shown that it
actually provides a strongly polynomial algorithm. For this an efficient way
to find an appropriate initial interval is given, then a strongly polynomial
bound on the number of iterations is provided.

####  4.2.1 Finding the Initial Interval

In order to find the initial interval, let us start with an arbitrary value
$\kappa_{0}\leq\kappa_{\max}$ and iterate the usual Newton steps on the
function $s(\kappa)$ until either

  1. 1.

a root of $s(\kappa)$ is found. Then the optimal solution of $0$ to the
original problem is found.

  2. 2.

a value with a subgradient $0$ is found. In this case the minimum of
$s(\kappa)$ has also been reached.

  3. 3.

a value with a subgradient of the opposite sign is found. Then
$[\kappa_{i-1},\kappa_{i}]$ (or $[\kappa_{i},\kappa_{i-1}]$ if
$\kappa_{i}<\kappa_{i-1}$) is an appropriate initial interval.

  4. 4.

$\kappa_{i}>\kappa_{\max}$. Then $[\kappa_{i-1},\kappa_{\max}]$ is an
appropriate initial interval.

####  4.2.2 Upper Bound on the Number of Iterations

######  Theorem 4.12.

The minimum of $s(\kappa)$ can be computed using the Handler–Zang method with
$\mathcal{O}(n^{4}m^{6}\log^{6}(m))$ iterations.

Note that during the execution of the algorithm, a set $X$ with
$\delta_{\tilde{c}}(X)=0$ can never be relevant when computing (26). Therefore
it can be rewritten as follows.

$s(\kappa)=\max\bigg{\\{}\kappa\frac{\partial_{\tilde{c}}(X)}{\delta_{\tilde{c}}(X)}-\frac{b(X)}{\delta_{\tilde{c}}(X)}:\delta_{\tilde{c}}(X)>0\bigg{\\}}.$
(29)

Thus, for any given value of $\kappa$ and set $X$ maximizing Equation (29),
the value $\frac{\partial_{\tilde{c}}(X)}{\delta_{\tilde{c}}(X)}$ is a
subgradient of $s(\kappa)$.

Now, let us assume that $\sigma^{*}$ is already known, and we are only looking
for the value of $\kappa^{*}$ for which $s(\kappa^{*})=\sigma^{*}$, i. e. we
are looking for a root of the function
$\overline{s}(\kappa):=s(\kappa)-\sigma^{*}$. This could also be computed by
the Discrete Newton Method outlined in Algorithm 5.

An important observation is the following. Let
$a^{\prime}_{1}<a^{\prime}_{2}<\cdots<a^{\prime}_{k}=\kappa^{*}$ be all the
_distinct_ values computed by the Handler–Zang method during the minimization
of $s(\kappa)$ and let
$a^{\prime}_{1}=\kappa_{0}<\kappa_{1}<\cdots<\kappa_{l}=\kappa^{*}$ be the
values computed by the Discrete Newton Method for finding the root of
$\overline{s}(\kappa)$ with the initial value $\kappa_{0}=a_{1}$. Then
$\kappa_{i}\leq a^{\prime}_{i}$ holds for all $i=1,\dots,k$, consequently
$k<l$.The same holds for the sequence of
$b^{\prime}_{1}>b^{\prime}_{2}>\cdots>b^{\prime}_{r}=\kappa^{*}$.

The Handler-Zang method updates either $a_{i}$ or $b_{i}$ in every iteration,
therefore we get that the number of its iteration is at most twice the number
of iterations taken by the Discrete Newton Method to find the root of
$\overline{s}(\kappa)$. An upper bound on the latter quantity is given below.

######  Theorem 4.13.

The root of $\overline{s}(\kappa)$ can be computed using the Discrete Newton
Method with $\mathcal{O}(n^{4}m^{6}\log^{6}(m))$ iterations.

1:$\kappa_{1}=a_{1}$, $i=1$

2: $\sigma_{i}=s(\kappa_{1})-\sigma^{*}$

3:while $\sigma_{i}>0$ do

4: $i=i+1$

5: $\kappa_{i}=\frac{b_{i-1}}{\partial_{i-1}}$

6: $\sigma_{i}=s(\kappa_{i-1})-\sigma^{*}$

7: $A_{i}=\operatorname*{arg\,max}_{A\subseteq
V}\frac{\kappa_{i}\partial_{\tilde{c}}(A)-b(A)}{\delta_{\tilde{c}}(A)}$

8:
$b_{i}=b(A_{i}),\quad\partial_{i}=\partial_{\tilde{c}}(A_{i}),\quad\delta_{i}=\delta_{\tilde{c}}(A_{i}),\quad
s_{i}=\frac{\partial_{i}}{\delta_{i}}$

Algorithm 5 Discrete Newton Method for $\overline{s}(\kappa)$

######  Claim 4.14.

$\frac{\sigma_{i+1}}{\sigma_{i}}+\frac{s_{i+1}}{s_{i}}\leq 1$ (30)

$\square$

An upper bound on the number of iterations is given below. For this purpose,
the indices are divided into parts, depending on the value of
$\frac{s_{i+1}}{s_{i}}$. Note that it is between $0$ and $1$, since $|s_{i}|$
is decreasing.

######  Lemma 4.15.

There are $\mathcal{O}(m^{4}\log^{4}(m))$ iterations such that
$\frac{s_{i+1}}{s_{i}}\leq\frac{2}{3}$.

###### Proof.

Let $i_{1},i_{2},\dots,i_{k}$ be the indices for which
$\frac{s_{i_{j}+1}}{s_{i_{j}}}\leq\frac{2}{3}$ holds and consider the sequence
$\delta_{i_{1}},\delta_{i_{2}},\dots,\delta_{i_{k}}$. By Theorem 2.8, there
exists a monotonic subsequence
$\delta_{i^{\prime}_{1}},\delta_{i^{\prime}_{2}},\dots,\delta_{i^{\prime}_{k^{\prime}}}$
of length $k^{\prime}=\left\lfloor\sqrt{k}\right\rfloor$.

Let us assume that all the subgradients computed by the Newton method are
positive i. e. $\partial_{i}>0$. (The case of negative subgradients is proved
the same way.)

##### Case 1.
$\delta_{i^{\prime}_{1}}\geq\delta_{i^{\prime}_{2}}\geq\cdots\geq\delta_{i^{\prime}_{s^{\prime}}}$.

Then

$\partial_{i^{\prime}_{j+1}}=s_{i^{\prime}_{j+1}}\delta_{i^{\prime}_{j+1}}\leq
s_{i^{\prime}_{j+1}}\delta_{i^{\prime}_{j}}\leq\frac{2}{3}s_{i^{\prime}_{j}}\delta_{i^{\prime}_{j}}=\frac{2}{3}\partial_{i^{\prime}_{j}}$

therefore

$\partial_{i^{\prime}_{j+2}}\leq\frac{2}{3}\partial_{i^{\prime}_{j+1}}\leq\frac{4}{9}\partial_{i^{\prime}_{j}}\leq\frac{1}{2}\partial_{i^{\prime}_{j}}$

holds for all $j=1,\dots,k^{\prime}-2$. Observe, that with

$\displaystyle b_{i}$ $\displaystyle=\tilde{c}(e_{i})\quad 1\leq i\leq|E|$
$\displaystyle x_{i}$ $\displaystyle=\begin{cases}1&e_{i}\in\varrho(A_{i})\\\
-1&e_{i}\in\delta(A_{i})\\\ 0&\text{otherwise}\end{cases}$

the values of $\partial_{i}$ are of the form required by Lemma 2.7. Therefore
we get $k^{\prime}=\mathcal{O}(m\log(m))$.

##### Case 2.
$\delta_{i^{\prime}_{1}}\leq\delta_{i^{\prime}_{2}}\leq\cdots\leq\delta_{i^{\prime}_{k^{\prime}}}$.

Similarly to Case 1, one can prove that there are $\mathcal{O}(m\log(m))$
indices such that
$\frac{4}{3}\delta_{i^{\prime}_{j^{\prime}}}\leq\delta_{i^{\prime}_{j^{\prime}+1}}$.

Now let us consider a subsequence of consecutive indices
$j_{1},j_{2},\dots,j_{h}$ such that
$\frac{4}{3}\delta_{j_{t}}>\delta_{j_{t+1}}$. Now we get that

$\frac{8}{9}\partial_{j_{t}}\geq\partial_{j_{t+1}}$

holds for all $1\leq t\leq h-1$. By Lemma 2.7, we get that the length of such
a subsequence is $\mathcal{O}(m\log(m))$. Therefore the total length
$k^{\prime}$ of the whole sequence is
$\mathcal{O}(m\log(m)\cdot~{}m\log(m))=\mathcal{O}(m^{2}\log(m^{2}))$. ∎

Now let us consider a sequence of consecutive iterations $i,\dots,i+l$ such
that $\frac{s_{j+1}}{s_{j}}\geq\frac{2}{3}$ for $j=i,\dots,i+l$. Note that by
Claim 4.14 $\frac{\sigma_{j+1}}{\sigma_{j}}\leq\frac{1}{3}$ also holds for
these indices.

######  Claim 4.16.

For any $j=i,\dots,i+l-1$, we have

$\kappa_{j+1}-\kappa_{i+l}\leq\frac{1}{2}(\kappa_{j}-\kappa_{i+l}).$ (31)

###### Proof.

The claim can easily be proved by the fact that

$\displaystyle\kappa_{j^{\prime}}-\kappa_{j^{\prime}+1}=\frac{\sigma_{j^{\prime}}}{s_{j^{\prime}}}=\frac{\sigma_{j^{\prime}-1}}{s_{j^{\prime}-1}}\cdot\frac{\sigma_{j^{\prime}}}{\sigma_{j^{\prime}-1}}\cdot\frac{s_{j^{\prime}-1}}{s_{j^{\prime}}}\leq\frac{\sigma_{j^{\prime}-1}}{s_{j^{\prime}-1}}\cdot\frac{1}{3}\cdot\frac{3}{2}=\frac{1}{2}(\kappa_{j^{\prime}-1}-\kappa_{j^{\prime}})$

holds for each $j^{\prime}=i,\dots,i+l-1$. ∎

######  Claim 4.17.

$WehaveF_{j}\geq 2F_{j+2}\quad\forall i\leq j\leq i+l-2,$

where

$F_{j}:=\sigma_{i+l}-(\sigma_{j}-(\kappa_{j}-\kappa_{i+l})s_{j}).$

###### Proof.

Note that

$\displaystyle\sigma_{j}-(\kappa_{j}-\kappa_{j+1})s_{j}=\sigma_{j}-\frac{\sigma_{j}}{s_{j}}s_{j}=0,$
$\displaystyle\sigma_{j}\geq\sigma_{i+l}\geq 0,$

and

$\displaystyle s_{j}\geq s_{j+1}$

hold for all $j=i,\dots,i+l$. Then the claim is proved as follows:

$\displaystyle F_{j}=$
$\displaystyle\sigma_{i+l}-(\sigma_{j}-(\kappa_{j}-\kappa_{i+l})s_{j})=\sigma_{i+l}-\sigma_{j}+(\kappa_{j}-\kappa_{i+l})s_{j}$
$\displaystyle=$
$\displaystyle\sigma_{i+l}-(\sigma_{j}-(\kappa_{j}-\kappa_{j+1})s_{j})+(\kappa_{j+1}-\kappa_{i+l})s_{j}\geq(\kappa_{j+1}-\kappa_{i+l})s_{j}$
$\displaystyle\geq$ $\displaystyle 2(\kappa_{j+2}-\kappa_{i+l})s_{j}\geq
2(\kappa_{j+2}-\kappa_{i+l})s_{j+2}$ $\displaystyle\geq$ $\displaystyle
2(\sigma_{i+l}-\sigma_{j+2})+2(\kappa_{j+2}-\kappa_{i+l})s_{j+2}$
$\displaystyle=$ $\displaystyle
2(\sigma_{i+l}-\sigma_{j+2}+(\kappa_{j+2}-\kappa_{i+l})s_{j+2})=2F_{j+2}.$

∎

######  Claim 4.18.

We have

$\displaystyle
F_{j}=\frac{\sigma_{i+l}\delta_{j}+b_{j}-\kappa_{i+l}\partial_{j}}{\delta_{j}}.$
(32)

Furthermore, the expression

$f(X):=\sigma_{i+l}\delta_{\tilde{c}}(X)+b(X)-\kappa_{i+l}\partial_{\tilde{c}}(X)$

appearing in the numerator in (32) is a submodular function.

###### Proof.

$\displaystyle F_{j}=$
$\displaystyle\sigma_{i+l}-(\sigma_{j}-(\kappa_{j}-\kappa_{i+l})s_{j})=\sigma_{i+l}-\frac{\partial_{j}}{\delta_{j}}\kappa_{j}+\frac{b_{j}}{\delta_{j}}+\kappa_{j}s_{j}-\kappa_{i+l}s_{j}$
$\displaystyle=$
$\displaystyle\sigma_{i+l}+\frac{b_{j}}{\delta_{j}}-\kappa_{i+l}(\frac{\partial_{j}}{\delta_{j}})=\frac{\sigma_{i+l}\delta_{j}+b_{j}-\kappa_{i+l}\partial_{j}}{\delta_{j}}$

and

$\displaystyle f(X)=$
$\displaystyle\sigma_{i+l}\delta_{\tilde{c}}(X)+b(X)-\kappa_{i+l}\partial_{\tilde{c}}(X)+\sigma_{i+l}\delta_{\tilde{c}}(Y)+b(Y)-\kappa_{i+l}\partial_{\tilde{c}}(Y)$
$\displaystyle=$
$\displaystyle\sigma_{i+l}(\delta_{\tilde{c}}(X)+\delta_{\tilde{c}}(Y))+(b(X)+b(Y))-\kappa_{i+l}(\partial_{\tilde{c}}(X)+\partial_{\tilde{c}}(Y))$
$\displaystyle\geq$ $\displaystyle\sigma_{i+l}(\delta_{\tilde{c}}(X\cup
Y)+\delta_{\tilde{c}}(X\cap Y))+(b(X\cup Y)+b(X\cap Y))$
$\displaystyle-\kappa_{i+l}(\partial_{\tilde{c}}(X\cup
Y)+\partial_{\tilde{c}}(X\cap Y))$ $\displaystyle=$
$\displaystyle\sigma_{i+l}\delta_{\tilde{c}}(X\cup Y)+b(X\cup
Y)-\kappa_{i+l}\partial_{\tilde{c}}(X\cup Y)$
$\displaystyle+\sigma_{i+l}\delta_{\tilde{c}}(X\cap Y)+b(X\cap
Y)-\kappa_{i+l}\partial_{\tilde{c}}(X\cap Y)$

∎

######  Theorem 4.19.

Let $i,i+1,\dots,i+l$ be consecutive indices such that
$\frac{\sigma_{j+1}}{\sigma_{j}}\leq\frac{1}{3}$. Then $l$ is at most
$\mathcal{O}(n^{4}m^{2}\log^{2}(m))$.

###### Proof.

The same technique is applicable here as in Lemma 4.15. Considering the
sequence of $\delta_{i},\delta_{i+1},\dots,\delta_{i+l}$ and using Theorem
2.8, a monotonic subsequence

$\delta_{j_{1}},\delta_{j_{2}},\dots,\delta_{j_{l^{\prime}}}$

of length $\lfloor\sqrt{l}\rfloor$ must exist.

##### Case 1.
$\delta_{j_{1}}\geq\delta_{j_{2}}\geq\cdots\geq\delta_{j_{l^{\prime}}}$.

Let us recall that $\delta_{j_{k}}\geq\frac{1}{\sqrt{2}}\delta_{j_{k+2}}$ and

$\frac{f(A_{j_{k}})}{\delta_{j_{k}}}=F{j_{k}}\geq
2F_{j_{k+2}}=2\frac{f(A_{j_{k+2}})}{\delta_{j_{k+2}}},$

therefore

$f(A_{j_{k}})\geq f(A_{j_{k+2}})$

holds for all $t\leq k\leq t+r-2$.

Then we can use Theorem 2.13 with
$T_{0}=A_{j_{t+r}},T_{1}=A_{j_{t+r-4}},\dots,T_{k}=A_{j_{t+r-4k}}$. The
conditions of theorem 2.13 hold true, firstly because

$\displaystyle f(A_{j_{k}})=$
$\displaystyle\sigma_{j_{t+r}}\delta_{j_{k}}+b_{j_{k}}-\kappa_{j_{t+r}}\partial_{j_{k}}=\delta_{j_{k}}\big{(}\sigma_{j_{t+r}}-(\sigma_{j_{k}}-(\kappa_{j_{k}}-\kappa_{j_{t+r}})s_{j_{k}})\big{)}$
$\displaystyle>$
$\displaystyle\delta_{j_{k}}\big{(}\sigma_{j_{t+r}}-(\sigma_{j_{k}}+(\kappa_{j_{k}}-\kappa_{j_{k+1}})s_{j_{k}})\big{)}\geq\delta_{j_{k}}\big{(}\sigma_{j_{t+r}}-0\big{)}>0$

hold for all $t\leq k\leq t+r-2$, and

$\displaystyle f(T_{0})=$ $\displaystyle
f(A_{j_{t+r}})=\sigma_{j_{t+r}}\delta_{j_{t+r}}+b_{j_{t+r}}-\kappa_{j_{t+r}}\partial_{j_{t+r}}$
$\displaystyle=$ $\displaystyle-
b_{j_{t+r}}+\kappa_{j_{t+r}}\partial_{j_{t+r}}+b_{j_{t+r}}-\kappa_{j_{t+r}}\partial_{j_{t+r}}=0$

holds for $k=t+r$, therefore $f(T_{0})=f_{\min}$ and
$f(T_{1})=f(A_{j_{t+r-4}})>0=-2f_{\min}$.

Secondly, because

$\displaystyle f(T_{k})=f(A_{j_{t+r-4k}})\geq
4f(A_{j_{t+r-4k+4}})=4f(A_{j_{t+r-4(k-1)}})=4f(T_{k-1})$

Due to Theorem 2.13, we have $r$ is at most
$4\binom{n+1}{2}+1=\mathcal{O}(n^{2})$.

In conclusion, the length of increasing subsequence
$\sqrt{l}=\mathcal{O}(n^{2})$, which means that the statement of the theorem
holds true in this case.

##### Case 2.
$\delta_{j_{1}}\leq\delta_{j_{2}}\leq\cdots\leq\delta_{j_{l^{\prime}}}$.

First, let $j_{t_{1}},j_{t_{2}},\dots,j_{t_{q}}$ denote the indices such that
$\sqrt[4]{2}\delta_{j_{t}}\leq\delta_{j_{t+1}}$. Then
$\delta_{j_{t_{k-4}}}\leq\frac{1}{2}\delta_{j_{t_{k}}}$ holds for all $5\leq
k\leq q$. Since $\delta_{j}$ is linear, using Lemma 2.7, it follows that $q$
is at most $\mathcal{O}(m\log(m))$.

On the other hand, let $j_{t},j_{t+1},\dots,j_{t+r}$ be a subsequence of
_consecutive_ indices such that $\sqrt[4]{2}\delta_{j_{t}}>\delta_{j_{t+1}}$.
Recall that $\delta_{j_{k}}\geq\frac{1}{\sqrt{2}}\delta_{j_{k+2}}$ and

$\frac{f(A_{j_{k}})}{\delta_{j_{k}}}=F{j_{k}}\geq
2F_{j_{k+2}}=2\frac{f(A_{j_{k+2}})}{\delta_{j_{k+2}}},$

therefore

$f(A_{j_{k}})\geq\sqrt{2}f(A_{j_{k+2}})$

hold for all $t\leq k\leq t+r-2$.

Then we can use Theorem 2.13 with
$T_{0}=A_{j_{t+r}},T_{1}=A_{j_{t+r-8}},\dots,T_{k}=A_{j_{t+r-8k}}$ similarly
to the first case and we get that $r$ is at most
$8\binom{n+1}{2}+1=\mathcal{O}(n^{2})$.

In conclusion, the length of increasing subsequence $\sqrt{l}$ is at most
$\mathcal{O}(n^{2}m\log(m))$, which proves the theorem. ∎

Finally, it follows from Lemma 4.15 and Theorem 4.19 that the number of
iterations the usual Discrete Newton Method is strongly polynomial. Thus, the
minimum of $s(\kappa)$ can be computed with
$\mathcal{O}(n^{4}m^{8}\log^{6}(m))$ submodular function minimization. In
summary, the following theorem is proved and an algorithm for finding
$\sigma^{*}$ is obtained.

######  Theorem 4.20.

The value of $\sigma^{*}$ along with maximizing sets $X,Y\subseteq V$ can be
computed in $\mathcal{O}(n^{4}m^{6}\log^{6}(m)\cdot(n^{2}+m\log^{2}(m)))$
submodular function minimization problems.

##  5 Balanced Integral Submodular Flows

A simple example of a graph having two nodes and two parallel edges shows that
the minimum spread solution is not always possible to be chosen to be
integral, even in case of simple network flows with integer supply vector.
This section shows how an integral flow of minimum (unweighted) spread can be
found.

From now on, let us assume that the submodular function $b$ is integral.

Just as in the weighted case, let $s(\kappa)$ be defined as the minimum value
$\sigma$ for which there exists a
$\left(\kappa\mathbbm{1},(\kappa+\sigma)\mathbbm{1}\right)$-bounded submodular
flow $x$. Note that $s(\kappa)$ can be computed by solving $\mathcal{O}(|A|)$
supermodular function minimization problems for any given $\kappa$. Clearly,

$\sigma^{*}=\min_{\kappa}s(\kappa)$

Note, that the function $s(\kappa)$ is a convex and piecewise linear.

######  Definition 5.1.

For an arbitrary integer $\kappa\in\mathbb{Z}$, let $s_{I}(\kappa)$ denote the
minimum value $\sigma$ for which there exists an
$\left(\kappa\mathbbm{1},(\kappa+\sigma)\mathbbm{1}\right)$-bounded _integral_
submodular flow $x\in\mathbb{Z}^{A}$.

######  Claim 5.2.

For any $\kappa\in\mathbb{Z}$, we have $s_{I}(\kappa)=\lceil s(\kappa)\rceil$.

###### Proof.

Clearly, $s_{I}(\kappa)\geq s(\kappa)$. On the other hand, the definition of
$s(\kappa)$ implies the existence of a
$\left(\kappa\mathbbm{1},\left(\kappa+s(\kappa)\right)\mathbbm{1}\right)$-bounded
submodular flow $x$. This flow is also bounded by the integer vectors
$\kappa\mathbbm{1}$ and $\left(\kappa+\lceil
s(\kappa)\rceil\right)\mathbbm{1}$, therefore — because of the integrality of
the submodular flow polyhedron [4] — an integer submodular flow must also
exist between these bounds. ∎

The claim above and the convexity of $s(\kappa)$ immediately give the
following.

######  Claim 5.3.

The spread $\sigma_{I}^{*}$ of the balanced integral submodular flow can be
computed as

$\sigma_{I}^{*}=\min\left\\{s_{I}(\lfloor\sigma^{*}\rfloor),s_{I}(\lceil\sigma^{*}\rceil)\right\\}=\min\left\\{\lceil
s(\lfloor\sigma^{*}\rfloor)\rceil,\lceil
s(\lceil\sigma^{*}\rceil)\rceil\right\\}$

. $\square$

##  6 Conclusions

In this paper, we extended the Balanced Network Flow Problem examined by
Scutellà and Klinz [16, 11] to submodular flows. A min-max formula and
strongly polynomial algorithm were presented to the problem as well as to its
weighted version. Finally, a strongly polynomial algorithm for Balanced
Integral Submodular Flow Problem was given.

### Acknowledgement

The work was supported by the Lendület Programme of the Hungarian Academy of
Sciences – grant number LP2021–1/2021 and by the Hungarian National Research,
Development and Innovation Office – NKFIH, grant number FK128673.

The authors would like to acknowledge the valuable suggestions of András Frank
and Kristóf Bérczi.

## References

  * [1] Ravindra K. Ahuja  “The balanced linear programming problem”  In _European Journal of Operational Research_ 101.1, 1997, pp. 29–38  DOI: https://doi.org/10.1016/S0377-2217(96)00142-7
  * [2] Paolo M. Camerini, Francesco Maffioli, Silvano Martello and Paolo Toth  “Most and least uniform spanning trees”  In _Discrete Applied Mathematics_ 15, 1986, pp. 181–197  DOI: https://doi.org/10.1016/0166-218X(86)90041-7
  * [3] Cees W. Duin and A. Volgenant  “Minimum deviation and balanced optimization: A unified approach”  In _Operations Research Letters_ 10.1, 1991, pp. 43–48  DOI: https://doi.org/10.1016/0167-6377(91)90085-4
  * [4] Jack Edmonds and Rick Giles  “A Min-Max Relation for Submodular Functions on Graphs”  In _Studies in Integer Programming_ 1, Annals of Discrete Mathematics  Elsevier, 1977, pp. 185–204  DOI: https://doi.org/10.1016/S0167-5060(08)70734-9
  * [5] Paul Erdős and George Szekeres  “A Combinatorial Problem in Geometry”  In _Classic Papers in Combinatorics_ Birkhäuser Boston, 1987, pp. 49–56  DOI: https://doi.org/10.1007/978-0-8176-4842-8˙3
  * [6] Annette M.. Ficker, Frits C.. Spieksma and Gerhard J. Woeginger  “Robust balanced optimization”  In _EURO Journal on Computational Optimization_ 6.3, 2018, pp. 239–266  DOI: https://doi.org/10.1007/s13675-018-0093-y
  * [7] András Frank  “Finding feasible vectors of Edmonds-Giles polyhedra”  In _Journal of Combinatorial Theory, Series B_ 36.3, 1984, pp. 221–239  DOI: https://doi.org/10.1016/0095-8956(84)90029-7
  * [8] GMichel X. Goemans, Swati Gupta and Patrick Jaille  “Discrete Newton’s Algorithm for Parametric Submodular Function Minimization”  In _Integer Programming and Combinatorial Optimization_ Springer International Publishing, 2017, pp. 212–227
  * [9] Gabriel Y. Handler and Israel Zang  “A dual algorithm for the constrained shortest path problem”  In _Networks_ 10.4, 1980, pp. 293–309  DOI: https://doi.org/10.1002/net.3230100403
  * [10] Alpár Jüttner  “On Resource Constrained Optimization Problems”  In _4th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications_ , 2005, pp. 136–143
  * [11] Bettina Klinz and Maria G. Scutellà  “A strongly polynomial algorithm for the Balanced network flow problem”, 1999
  * [12] Wu Longshu  “An Efficient Algorithm for the Most Balanced Spanning Tree Problems”  In _Advanced Science Letters_ 11, 2012, pp. 776–778  DOI: https://doi.org/10.1166/asl.2012.3033
  * [13] Silvano Martello, William R. Pulleyblank, Paolo Toth and Dominique de Werra  “Balanced optimization problems”  In _Operations Research Letters_ 3.5, 1984, pp. 275–278  DOI: https://doi.org/10.1016/0167-6377(84)90061-0
  * [14] James Orlin  “A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization”  In _Mathematical Programming_ 118, 2009, pp. 237–251  DOI: https://doi.org/10.1007/s10107-007-0189-2
  * [15] Tomasz Radzik  “Fractional combinatorial optimization”  In _Handbook of Combinatorial Optimization_ Springer US, 1998, pp. 429–478  DOI: https://doi.org/10.1007/978-1-4613-0303-9
  * [16] Maria G. Scutellà  “A Strongly Polynomial Algorithm for the Uniform Balanced Network Flow Problem”  In _Discrete Applied Mathematics_ 81, 1998, pp. 123–131  DOI: https://doi.org/10.1016/S0166-218X(97)88001-8

## Appendix

##  Appendix A Handler–Zang Method for Convex Function
Minimization

This section describes a natural approach to minimize a single variable convex
function. In the case of piecewise linear functions, it is able to find the
exact optimum in a finite number of iterations, which makes it a useful tool
for solving certain parametric combinatorial optimization problems. Its first
use in this scenario is probably due to Handler and Zang [9].

Let $f:\mathbb{R}\to\mathbb{R}$ be a convex function, let $\partial f(x)$
denote the set of its subgradients at $x$, and let us consider Algorithm 6. An
iteration of the algorithm is shown in Figure 1.

1:Let $a_{1},b_{1}\in\mathbb{R}$ such that $a_{1}\leq\arg\min f\leq b_{1}$

2:Let $\alpha_{1}\in\partial f(a_{1})$ and $\beta_{1}\in\partial f(b_{1})$

3:$i:=1$

4:repeat

5:
$c_{i}:=\frac{f(b_{i})-f(a_{i})+\alpha_{i}a_{i}-\beta_{i}b_{i}}{\alpha_{i}-\beta_{i}}$

6:
$\sigma_{i}:=\frac{\alpha_{i}f(b_{i})-\beta_{i}f(a_{i})+\alpha_{i}\beta_{i}(a_{i}-b_{i})}{\alpha_{i}-\beta_{i}}$

7: if $f(c_{i})=\sigma_{i}$ then RETURN $c_{i}$

8: Let $\gamma_{i}\in\partial f(c_{i})$

9: if $\gamma_{i}<0$ then

10: $a_{i+1}:=c_{i}$, $\alpha_{i+1}:=\gamma_{i}$,

11: $b_{i+1}:=b_{i}$, $\beta_{i+1}:=\beta_{i}$

12: else

13: $a_{i+1}:=a_{i}$, $\alpha_{i+1}:=\alpha_{i}$,

14: $b_{i+1}:=c_{i}$, $\beta_{i+1}:=\gamma_{i}$

15: $i\longleftarrow i+1$

Algorithm 6 Handler-Zang method

######  Claim A.1.

The following statements are true

  * •

$a_{1}\leq a_{2}\leq a_{3}\leq\cdots$

  * •

$b_{1}\geq b_{2}\geq b_{3}\geq\cdots$

  * •

$\alpha_{1}\leq\alpha_{2}\leq\alpha_{3}\leq\cdots$

  * •

$\beta_{1}\leq\beta_{2}\leq\beta_{3}\leq\cdots$

  * •

For each iteration $i$ either of the following holds

    1. 1.

$a_{i}<a_{i+1}$ and $\alpha_{i}<\alpha_{i+1}$

    2. 2.

$b_{i}>b_{i+1}$ and $\beta_{i}>\beta_{i+1}$

  * •

The subgradients $\gamma_{i}\quad(i=1,2,\dots)$ computed during the execution
are all different.

Figure 1: An iteration of the Handler-Zang method

######  Claim A.2.

If $f$ is a piecewise linear convex function, then Algorithm 6 finds the
minimum of $f$ in finite number of steps, and the number of iterations is at
most the number of linear segments of $f$. $\square$

In applications in combinatorial optimization, the function $f$ is typically
given implicitly in the form of

$f(x):=\max\\{a_{i}+b{{}_{i}}x:i\in{\cal I}\\}$

by a subroutine that is able to find this maximum for any given value of $x$.
(The index set $\cal I$ may be exponentially large). Note that for the
maximizing $i\in{\cal I}$, the value $b_{i}$ is a subgradient of $f(x)$.

Even when the function has exponentially many linear segments, a strongly
polynomial bound on the number of iterations can be given for certain classes
convex functions, see e. g. [10].