Concave Flow on Small Depth Directed Networks

arXiv:1704.07791v1 [cs.DS] 25 Apr 2017

Tung Mai
Georgia Tech
tung.mai@cc.gatech.edu

Richard Peng
Georgia Tech
rpeng@cc.gatech.edu

Anup B. Rao
Georgia Tech
arao89@gatech.edu

Vijay V. Vazirani
Georgia Tech
vazirani@cc.gatech.edu
April 26, 2017

Abstract
Small depth networks arise in a variety of network related applications, often in the form of
maximum flow and maximum weighted matching. Recent works have generalized such methods
to include costs arising from concave functions. In this paper we give an algorithm that takes
a depth D network and strictly increasing concave weight functions of flows on the edges and
computes a (1−ǫ)-approximation to the maximum weight flow in time mDǫ−1 times an overhead
that is logarithmic in the various numerical parameters related to the magnitudes of gradients
and capacities.
Our approach is based on extending the scaling algorithm for approximate maximum weighted
matchings by [Duan-Pettie JACM‘14] to the setting of small depth networks, and then generalizing it to concave functions. In this more restricted setting of linear weights in the range
[w min , w max ], it produces a (1 − ǫ)-approximation in time O(mDǫ−1 log(w max /w min )). The
algorithm combines a variety of tools and provides a unified approach towards several problems
involving small depth networks.

1

Introduction

Combinatorial problems have traditionally been solved using combinatorial methods, e.g., see
[Sch03]. Aside from providing many state-of-the-art results, these methods also have the advantages of simplicity and interpretability of intermediate solutions. Recently, algorithms that
utilize continuous methods have led to performances similar or better than these combinatorial
methods [CKM+ 11, Mad13, ZO15]. A significant advantage of continuous approaches is that they
extend naturally to general objective functions, whereas in combinatorial algorithms there is much
difference, for example, between even finding a maximum flow and a minimum cost flow.
This paper is motivated by recent works that used accelerated gradient descent to obtain
O(mǫ−1 log n) time routines for computing approximate solutions of positive linear programs [ZO15,
WRM15]. Such linear programs include in particular (integral) maximum weighted matchings on
bipartite graphs, and fractional weighted matchings on general graphs. These algorithms, as well
as earlier works using continuous methods for the maximum weighted matching problems [AG14],
represent a very different approach that obtained bounds similar to the result by Duan and Pettie [DP14]; the latter computed similar approximations using combinatorial methods. We study
this connection in the reverse direction to show that the augmenting path based approaches can be
extend to 1) small depth, acyclic networks, and 2) more general cost objectives. Formally, given a
DAG with source s and sink t, along with capacities c e and differentiable concave functions fe on
each
P edge, we want to find a flow from s to t that obeys capacity c e and maximizes the function
e fe (x e ). Our main result to this direction is:
Theorem 1.1. Given a depth D acyclic network with positive capacities and concave cost functions
whose derivatives are between w min and w max and queryable in O(1) time, ConvexFlow returns
a (1 − ǫ)-approximation to the maximum weighted flow in O Dmǫ−1 log(w max /w min ) log n time.

We note that the logarithmic dependency on w max /w min is common in scaling algorithms
for flows: the case of linear costs corresponds to fe (x e ) = w e x e for scalars w e , and in turn
w min = mine w e and w max = maxe w e . We will discuss the relation between this formulation and
other flow problems, as well this dependency on weights in Section 1.2.
1. Initialize flow x , potentials p, step size δ
2. Repeat until δ is sufficiently small:
(a) Repeat O(1/ǫ) steps:
i. Compute eligible capacities on the edges, forming the eligible graph.
ii. Send a maximal flow in the eligible graph.
iii. Recompute eligible graph, adjust potentials of vertices unreachable from s.
(b) Reduce δ, and adjust the potentials.
Figure 1: Algorithmic Template for Our Routines

The main components of our algorithm are in Figure 1. It involves the construction and flow
routing on an eligiblility graph, which consists of all positive capacitiated edges calculated from a set
of eligibility rules. Note that aside from the blocking-flow computation on this graph in Step 2(a)ii,
1

all other steps are local steps based on values on an edge, potentials of its two end points, and an
overall step size. This algorithm in its fullest generalization is in Figure 8 in Section 4.
The paper is organized as follows. In Section 2 we describe the simplest variant: max weight
flow on unit-capacity, small depth networks where the cost functions on edges are linear. The main
reason for presenting this simple setting is to show how we trade running time with accuracy by
appropriately relaxing eligibility conditions for edges. In Section 3, we extend our algorithm to
situations with widely varying edge weights via a scaling scheme. We then extend the result to
concave functions in Section 4, leading to our main result as stated in Theorem 1.1.

1.1

Our Techniques

Our main technical contribution is a method for combining augmenting paths algorithms with
primal-dual schemes for flows with costs. We combine blocking flows, which are essentially maximal sets of augmenting paths, with the weight functions on edges via eligibility rules that dictate
which edge in the residual graph can admit flow based on the current primal / dual solution. Invariants that follow from these eligibility rules then allow us to maintain approximate complementary
slackness between the primal and dual solutions. In turn, these yield approximation guarantees.
Our eligibility rules are directly motivated by the scaling algorithms for approximate maximum
matching [DP14], which is in turn based on scaling algorithms for maximum weighted matchings [GT89, GT91, Gab17]. However, the fact that augmenting paths can contain edges from
different depth levels pose several challenges. Foremost is the issue that a very heavily weighted
edge may cause flow to go through a lightly weighted edge. As a result, we need to find a way to
work around the key idea from [DP14] of relating the weight of an edge to the first time a flow
passes through it. We do so by using paths as the basic unit by which we analyze our flows, and
analyzing the entire history of paths going through an edge (see Section 3.3 for details).
We will develop our algorithms first in the case where all weights on edges are linear, and then
extend them to concave functions. These extensions are obtained by viewing each edge with nonlinear cost functions as a collection of edges with differing weights and infinitesimal capacities, and
then simulating a continuous version of our linear algorithm through blocking flows.

1.2

Related Works

As our results combine techniques applicable to a wide range of combinatorial problems, our results
have similarities, but also differ, from many previous works. An incomplete list of them is in
Figure 2. In order to save space, we use Õ(f (n)) to hide terms that are polylog(f (n)): this is a
widely used convention for the more numerical variants of these objectives, and here mostly hides
factors of log n.
While the guarnatees of many of the algorithms listed here are stated for inputs with integer
capacities / costs [GT89, GR98, LS14], their running times are equivalent to producing 1 ± ǫapproximates with poly(log(ǫ−1 )) overhead in running time.
Our guarantees, which contain poly(ǫ−1 ) in the running time terms, closest resemble the approximation algorithms for weighted matchings [DP14, ZO15, AG14] and flows on small depth
networks [Coh95]. These running times only outperform the routines with poly(log(ǫ−1 )) depdencies for mild ranges of ǫ. In such cases, the solution can differ significantly point-wise from the
optimum: for example, deleting ǫ-fraction of a maximum cardinality matching still gives a solution
that’s within 1 ± ǫ of the optimum. As a result, the barriers towards producing exact solutions in
2

reference
[GR98]
[Orl13]
[Coh95]
[Pen16]
our work
[LS14]
[Orl93]
[GT87]
our work
[GT89]
[DP14]
[ZO15]
[AG14]
our work
[Hoc07]
[Vég12]
our work

objective
flow amount
flow amount
flow amount
flow amount
flow amount
min linear cost
min linear cost
min linear cost
max linear weight
matching weight
matching weight
matching weight
b-matching weight
b-matching weight
concave/convex
min separable convex cost
max concave weight

graph
any
any
small depth
undirected
small depth
any
any
any
small depth
any
any
bipartite 2
any
bipartite
any
any
small depth

approximation
1 ± ǫ in value
exact
1 ± ǫ in value
1 ± ǫ in value
1 ± ǫ in value
1 ± ǫ in value
exact
exact
1 ± ǫ in value
1 ± ǫ in value
1 ± ǫ in value
1 ± ǫ in value
1 ± ǫ in value
1 ± ǫ in value
1 ± ǫ pointwise
exact
1 ± ǫ in value

runtime 1
Õ(m3/2 log(ǫ−1 ))
Õ(mn)
Õ(mD 2 ǫ−3 )
Õ(mǫ−3 )
Õ(mDǫ−1 )
Õ(m3/2 log(ǫ−1 ))
Õ(m2 )
Õ(mn)
Õ(mDǫ−1 )
Õ(mn1/2 log(ǫ−1 ))
O(mǫ−1 log(ǫ−1 ))
Õ(mǫ−1 )
Õ(mpoly(ǫ−1 ))
Õ(mǫ−1 )
Õ(m2 log(ǫ−1 ))
≥ O(n4 )
Õ(mDǫ−1 ) 3

Figure 2: Results Related to Our Algorithm

strongly polynomial time [Hoc07] are circumvented by these assumptions, especially the bounds on
the minimum and maximum gradients. These bounds are natural generalizations of the bounds on
costs in scaling algorithms for flows with costs [GT89]. In some cases, they can also be removed
via preprocessing steps that find poly(n) crude approximations to the optimum, and trim edge
weights via those values [CKM+ 11, DP14, Pen16]. In particular, if all the capacities are integers,
we can increase the minimum weight, or gradient, in a way analogous to the matching algorithm
from [DP14].
Lemma 1.2. If all capacities are integers and the functions fe are non-negative and increasing,
then we can assume
ǫw max
P
,
w min ≥
O (m2 · e c e )
P
2
or w max /w min ≤ O( mǫ · e c e ) without perturbing the objective by a factor of more than 1 ± ǫ.

Proof. First, note that the assumption about integral capacities means that there exists a feasible
flow that routes at least 1/m2 per edge, and such a flow, x ′ , can be produced using a single
depth-first search in O(m) time.
We will fix the gradients to create functions f whose gradients are all within poly(m, ǫ−1 ) of
 ǫ 
def
w
b = max f
.
e
m2
1

Many of the approximate algorithms assume integer capacities/weights, and have factors log C and/or log N in
their running times, where C and N are the largest capacity and weight respectively. We omit those factors due to
space constraints: they are discussed as dependencies on the accuracy ǫ in the text before Lemma 1.2.
2
This algorithm also can produce fractional matching solutions on general graphs.
3
There is a hidden factor of logarithm of the ratio between max and min gradients.

3

First, note that OP T ≥ w
b since the functions are non-negative. So we can add Pǫwbc e to the gradient
e
of all the functions without changing the optimum by more than ǫw
b ≤ ǫOP T additively. Formally
the functions:
ǫw
b
def
.
f e (x) = fe (x) + x · P
e′ c e′

with associated maximum OP T satisfies OP T ≤ OP T ≤ (1 + ǫ)OP T .
To fix the maximum gradient, consider the truncated functions
(
f e (x)
if x ≥ mǫ2 , and
def

.
fbe (x) = xm
2
ǫ
if x ≤ mǫ2
ǫ · f e m2

It can be checked that fbe (x) ≤ f e (x) at all points, and that the maximum gradient of fbe (x) is
bounded by
 ǫ 

xm2
2 −1
· fe
≤
O
m
ǫ
w
b
.
ǫ
m2
[
[
So it remains to show that OP
T , the maximum with the functions fb satisfies OP
T ≥ (1 − ǫ)OP T .
For this, consider the optimum solution to OP T , x , the solution
(1 − ǫ) x + ǫx ′

is feasible because it’s a linear combination of two feasible solutions, has objective at least 1 − ǫ
times the objective of x due to the concavity and monotonicity of f , and has flow at least ǫ/m2
per edge. The result then follows from observing that fbe (x) = f e (x) for all x ≥ ǫ/m2 .

Remark By Lemma 1.2, if all capacities are integer, the running time of our result can be written
as Õ(Dmǫ−1 log C), where C is the largest capacity.
Our assumption on the topology of the graph follows the study of small depth networks
from [Coh95], which used the depth of the network to bound the number of (parallel) steps required by augmenting path finding routines. From an optimization perspective, small depth is also
natural because it represents the number of gradient steps required to pass information from s to t.
Gradient steps, in the absence of preconditioners, only pass information from a node to its neighbor, so diameter is kind of required for any purely gradient based methods The acyclicity requirement is a consequence of our adaptation of tools from approximating weighted matchings [DP14],
and represent a major shortcoming of our result compared to exact algorithms for minimum cost
flow [Orl93] and convex flows [Hoc07, Vég12]. However, as we will discuss in Appendix A, there
are many applications of flows where the formulations naturally lead to small depth networks.

2

Simple Algorithm for Unit Capacities and Linear Weights

In this section, we propose a simple (1 − ǫ) approximation algorithm for the case of fe (·) being
linear functions, and all capacities are unit. This assumption means we can write the cost functions
as:
fe (x e ) = w e x e
for some w e ≥ 0. Under these simplifications, the linear program (LP) that we are solving and its
dual become:
4

max

X
e

∀u,
∀e,

X
vu

x vu =

X

min

w ex e
X

ye

e

∀e,

x uv

uv

0 ≤ xe ≤ 1

pv − pu + y e ≥ w e

ps = pt

∀e,

y e ≥ 0.

We add a dummy directed edge from t to s with infinite capacity to ensure flow conservation
at each vertex. For every edge e we mention in the paper, we implicitly assume that e = uv is an
edge in the original network and e 6= ts, unless otherwise stated. The dual inequality involving y e
is equivalent to:
y e ≥ w e + pu − pv,
The RHS is critical for our algorithm and its analysis. We will define it as the reduced weight of
the edge, w pe :
w pe = w e + p u − p v .

Note that the choice of w pe uniquely determines the optimum choice of y e through y e ← max 0, w pe .
To find an optimum flow on these networks it is sufficient to obtain feasible pairs x and p, y
that satisfy the following complementary slackness conditions:
1. For all e, if x e = 0, then y e = 0, which is equivalent to w pe ≤ 0.
2. For all e, if x e = 1 then y e = w pe , which is equivalent to w pe ≥ 0.
The role of these values of w pe can be further illustrated by the following Lemma, which is
widely used in scaling algorithms.
Lemma 2.1. For any flow x for which the flow conservation is satisfied, and any potential p such
that p t = p s , we have:
X
X
w ex e =
w pe x e .
e

e

Proof. Expanding the summation gives
X
X
X
X
w ex e +
x ep u −
x ep v .
w pe x e =
e

e=uv

e=uv

e

Rearranging the last terms gives
X
u

pu

X
uv

x uv −

X
vu

x vu

!

,

which we know is 0 for every u 6= s, t. We also have that the amount of flow leaving s is same as
the amount of flow entering t, and p s = p t so the total contribution of these terms is 0.

5

Note that if p s = 0 and w pe is close to 0 for each e in a path from s to some u, the total
reduced cost of the path is close to p u . This is the view taken by most primal-dual algorithms for
approximate flows: conditions are imposed on valid paths in order to make p u s emulate max weight
residual paths to the source. These routines then start with p t set to very large, and maintaining
a complementary primal/dual pair while gradually reducing p t . Shortest path algorithms such as
the network simplex method and the Hungarian algorithm fall within this framework [AMO93,
Chapter 12]. Such algorithms produce exact answers, but may take Ω(n) steps to converge even in
the unit weighted case due to very long augmenting paths.
The central idea in our algorithms is to regularize these complementary slackness conditions.
Specifically, we relax the x e = 0 case from w pe ≤ 0 to w pe ≤ δ, for some δ which we eventually set to
ǫw min . We may assume that all the weights are integer multiples of δ since the additive rounding
error of each weight w e is at most ǫw e . We use a set of eligibility rules to define when we can send
flows along edges, or whether an arc is eligible. The modified eligibility conditions are shown in
Figure 3.

1. Forward edge: if x e = 0, can send flow along u → v if w pe = δ.
2. Backward edge: if x e = 1, can send flow back from v → u if w pe = 0.
Figure 3: Eligiblity Rules for Simple Algorithm on Unit Capacity Networks with Linear Weights.

(A1) If x e = 1, then w pe ≥ 0.
(A2) If x e = 0, then w pe ≤ δ.
Figure 4: Relaxed Invariant for Simple Algorithm on Unit Capacity Networks with Linear Weights.
These rules leads our key construct, the eligible graph:
Definition 2.2. Given a graph G and a set of eligibility rules, the eligible graph consists of all
eligible residual arcs with positive capacities, equaling to the amount of flow that can be routed on
them. A vertex v is an eligible vertex if there exists a path from s to v in the eligible graph.
The main idea behind working on this graph is that this approximate invariant can be maintained analogously to exact complementary slackness.
This leads to an instantiation of the algorithmic template from Figure 1. Its pseudocode is
given in Figure 5.
The key property given by the introduction of δ is after sending 1 unit of flow along a maximal
collection of paths, t is no longer reachable from s in the eligible graph. We can show this from
the observation that all edges in a path that we augment along become ineligible. For an eligible
forward edge uv, x uv = 0 and w puv = δ. Therefore, after augmentation, x uv = 1 and vu is ineligible.
A similar argument can be applied for an eligible backward edge vu to show that after augmentation
the residual forward edge uv is also ineligible.
6

x = SimpleFlow (G, s, t, {w e } , w min , w max , ǫ)
Input: Unit capacity directed acyclic graph G from s to t,
Weights w e for each edge e, along with bounds w min = mine w e and w max = maxe w e .
Error tolerance ǫ.
Output: (1 − ǫ) approximate maximum weight flow x .
1. Compute levels lu of the vertices u (length of a longest path from s to u).
Initialize x e = 0, p u = w max · lu , δ = ǫw min .
2. Repeat until p t = 0:
(a) Eligibility labeling: Compute the eligible graph.
(b) Augmentation: Send 1 unit of flow along a maximal collection of edge-disjoint paths
in the eligible graph.
(c) Dual Adjustment: Recompute the eligible graph, for each vertex u unreachable from
s, set p u ← p u − δ.
Figure 5: Simple Algorithm Based on the Eligibility Conditions From Figure 3
This fact plays an important role in our faster convergence rate:
Lemma 2.3. The running time of the algorithm given in Figure 5 is O(Dw max m/ǫw min ) where
D is the depth of the network.
Proof. The algorithm starts with p t = Dw max and in each iteration, p t is decreased by δ.
Therefore, the number of iterations is Dw max /δ. Since in each iteration it takes O(m) to find
a maximal set of disjoint augmenting paths using depth-first search, the total running time is
O(Dw max m/ǫw min ).
We also need to check that our eligibility rules and augmentation steps indeed maintain the
invariants throughout this algorithm.
Lemma 2.4. Throughout the algorithm, the invariants from Figure 4 are maintained.
Proof. It is easy to check that at the beginning of the algorithm, the invariants are satisfied. We
will show by induction that dual adjustments and augmentations do not break them. Assume the
two conditions hold before a dual adjustment step. Notice that a dual adjustment can only change
reduced weights of edges that have exactly one eligible endpoint. For an edge e = uv, we consider
2 cases:
• u is eligible, and v is ineligible: a dual adjustment step decreases p v , and thus increases w pe .
Condition (A1) still holds because the reduced weight increases. Condition (A2) still holds
because reduced weight can only increase until it is equal to δ and both u and v are eligible.
• v is eligible, and u is ineligible: a dual adjustment step decreases p u , and thus decreases
w pe . Condition (A1) still holds because the reduced weight can only decrease until it is equal
7

to 0 and both u and v are eligible. Condition (A2) still holds because the reduced weight
decreases.
Now assume that the two conditions hold before an augmentation step, and notice that we only
send flow along eligible edges. For an edge e with x e = 0 before augmentation, the eligibility
condition is w pe = δ, thus after augmentation x e = 1 and condition (A1) is satisfied. For an edge
e with x e = 1 before augmentation, the eligibility condition is w pe = 0, thus after augmentation
x e = 0 and condition (A2) is satisfied.
It remains to bound the quality of the solution produced. Once again, the invariants from
Figure 4 play crucial roles here.
Lemma 2.5. If all the invariants and feasibility conditions hold when the algorithm terminates
with p s = p t , then the solution produced, x , is feasible and (1 − ǫ)-optimal.
Proof. The flow x is feasible because in each augmentation step we only send one unit of flow along
a path in the residual graph.
Let x ∗ be any other st flow obeying the capacities. Our goal is to show that
X
X
w e x e ≥ (1 − ǫ)
w e x ∗e .
e

e

To do so, we first invoke Lemma 2.1, which allows us consider the weights w pe instead. We
invoke the invariants based on the two cases:
1. If x e = 1, then x ∗e ≤ x e since the edges are unit capacitated. The invariant also gives w pe ≥ 0,
which implies
x e w pe ≥ x ∗e w pe .
2. If x e = 0, then w pe x e = 0. The invariant gives w pe ≤ δ, which combined with x ∗e ≥ 0 gives:
x e w pe = 0 ≥ x ∗e (w pe − δ) .
Furthermore, since δ ≤ ǫw e , this also implies
x e w pe ≥ x ∗e w pe − ǫw e x ∗e .
Summing the implications of these invariants across all edges gives
X
X
X
X
X
x ∗e w e .
x e w pe ≥
x ∗e w pe − ǫ
x ∗e w e = (1 − ǫ)
x ew e =
e

e

e

e

8

e

3

Scaling Algorithm for Linear Weights

In this section, we show how to improve the running time of the algorithm in the previous section
through scaling. The scaling algorithm makes more aggressive changes to vertex potentials p u at
the beginning, and moves to progressively smaller changes. To be more precise, the algorithm starts
with δ0 = ǫw max and ends with δT = ǫw min , and the value of δ is halved each scale. Assume ǫ and
w max /w min are powers of 2, this immediately implies
T = log (w max /w min ) .
The vertex potentials are also initialized in a similar way, i.e p u = w max · lu for all u. Scale
i > 0 starts with
p t = Dw max /2i + 2Dδi
and ends when
p t = Dw max /2i+1 .
The change in step sizes leads to more delicate invariants. Instead of having a sharp cut-off at δ as
in the single-scale routine, we further utilize δi to create a small separation between edges eligible
in the forward and backward directions.
Between scales, we make adjustments to all potentials to maintain the invariants. Pseudocode
of this routine is given in Figure 6.
The rest of this section is a more sophisticated analysis built upon Section 2 and the scaling
algorithms from [DP14], leading to the following main claim:
Theorem 3.1. For any ǫ < 1/10,
 ScalingFlow returns x that is an (1 − 8ǫ)-approximation in
−1
O Dmǫ log(w max /w min ) log n time.

A main issue in setting up the invariants, as well as the overall proof, is that errors from the
iterations accumulate. Here we need an additional definition about the last time forward flow as
pushed on an edge.
Definition 3.2. During the course of the algorithm, for each edge e = uv, define scale(e) to be
the the largest scale j such that j is at most i, the current scale, and there is a forward flow from
u to v at scale j. Define scalef (e) to be the final value of scale(e) when the algorithm terminates.

Note that scale(e) resets to i if uv is used in the blocking flow generated on Line 2(a)ii at scale
i. For simplicity, we use δe to denote δscale(e) , δef to denote δscalef (e) , and le to denote lv − lu . The
key eligibility rules and invariants are in Figure 7.
The intricacies in Condition (B1) is closely related to the changes in the dual rescaling step
from Line 2(b)i. In particular, Condition (B2), w pe < 2δi , may be violated if δi is halved. The
dual rescaling on Line 2(b)i is in place precisely to fix this issue by lowering w pe . It on the other
hand causes further problems for lower bounds on w pe , leading to modifications to Condition (B1)
as well. We first verify that these modified invariants are preserved by the dual rescaling steps.

3.1

Dual Rescaling Steps

Lemma 3.3. The dual rescaling step on Line 2(b)i of Figure 7 maintain invariants (B1) and (B2).

9

ScalingFlow (G, s, t, {w e , c e } , w min , w max , ǫ)
Input: Directed acyclic graph G from s to t,
weights w e for each edge e, along with bounds w min = mine w e and w max = maxe w e ,
capacities c e for each edge e,
error tolerance ǫ.
Output: (1 − ǫ) approximate maximum weight flow x .
1. Compute levels lu of the vertices u (length of a longest path from s to u).
Initialize x = 0, p u = w max · lu , δ0 = ǫw max .
max
2. For i from 1 to T = log w
w min :

(a) Repeat until p t =

Dw max
2i+1

if i < T or until p t = 0 if i = T :

i. Eligibility labeling: Compute the eligible graph based on the eligibility rules:
A. uv is eligible in the forward direction if δi ≤ w puv ,
B. a backward edge vu is eligible if w puv ≤ 0.
ii. Augmentation: Send a blocking flow in the eligible graph.
iii. Dual Adjustment: Recompute the eligible graph, for each vertex u unreachable
from s, set p u ← p u − δi .

(b) If i < T :

i. Dual Rescale: p u ← p u + δi lu ,
ii. δi+1 ← δ2i .
Figure 6: Scaling Algorithm Based on the Eligibility Condition From Figure 7.
′

Proof. We start with Condition (B2). If w pe ≤ 2δi , then if we pick p ′ such that w pe ≤ w pe − δi , we
get:
′
w pe ≤ δi = 2δi+1 .
This is done by updating vertex potential p u ← p u + δi lu for each vertex u at the end of scale i.
It remains to check that the condition
w pe ≥ −3le (δe − δi ) − δi
does not break by decreasing p u − p v by le δi :
− 3le (δe − δi ) − δi − le δi
= −3le δe + 2le δi − δi

= −3le δe + 4le δi+1 − 2δi+1

≥ −3le (δe − δi+1 ) − δi+1 .
where the last line follows because le ≥ 1.
10

1. Forward edge: if x e < c e , u → v is eligible if w pe ≥ δi .
2. Backward edge: if x e > 0, v → u is eligible if w pe ≤ 0.

(B1) If x e > 0, then w pe ≥ −3le (δe − δi ) − δi .
(B2) If x e < c e , then w pe ≤ 2δi .
Figure 7: Relaxed Invariant and Corresponding Eligibility Rules for Scaling Algorithm on Non-unit
Capacity Networks with Linear Weights.

3.2

Blocking Flows

Our algorithm also incorporates more general capacities c e . The changes caused by this in the
linear programming formulations are:
1. In the primal, the capacity constraints become 0 ≤ x e ≤ c e ,
P
2. the dual objective becomes e c e y e .

This extension can be incorporated naturally: instead of finding a maximal set of edge-disjoint
augmenting paths, we find a blocking flow from s to t. Blocking flows can also be viewed as
maximal sets of paths when the edges are broken down into multi-edges of infinitesimal capacities.
They can be found in O(m log n) time using dynamic trees [ST83], and therefore offer similar levels
of theoretical algorithmic efficiency.
In the unit capacity case, an augmentation along any path in the residual graph destroys all
eligible edges in the path, and the asymmetry of the eligibility condition means the new reverse edges
are also ineligible. However, when we move to general capacities, an augmentation may destroy just
a single edge on the path. As a result, it’s simpler to work with the following equivalent definition
of blocking flows.
Definition 3.4. A blocking flow on a graph G is a flow such that every path from s to t goes
through a fully saturated edge.
We first verify that this definition also maintains all the invariants both after augmentation and
dual adjustments. These proofs closely mirror those of Lemma 2.4.
Lemma 3.5. An augmentation by a blocking flow in the eligible graph, as on Line 2(a)ii, maintains
the invariant.
Proof. The algorithm only sends flow through eligible edges. Consider an edge uv on a blocking
flow
1. If the augmentation sends flow from u to v, then uv is an eligible forward edge, and w puv ≥ δi .
After augmentation, condition (B1) must hold.
11

2. If the augmentation sends flow from v to u, then vu is an eligible backward edge, and 0 ≥ w puv .
After augmentation, condition (B2) must hold.
Therefore, all edges on a blocking flow satisfy the set of reduced weight conditions after augmentation.
Lemma 3.6. A dual adjustment step, as specified on Line 2(b)i, maintains the invariant.
Proof. Notice that a dual adjustment can only change the effective reduce weights of edges that
have exactly one eligible endpoint. For an edge e = uv in the graph, we consider 2 cases:
• u is eligible, and v is ineligible: a dual adjustment step decreases p v , and thus increases w pe .
– if x e = c e then condition (B1) still holds because w pe increases.
– if x e < c e then we know that uv is in the residual graph and ineligible. Since uv is
ineligible, w pe must be less than δi . Condition (B2) still holds because w pe can only
increase until it is at least δi and e becomes eligible.
• v is eligible, and u is ineligible: a dual adjustment step decreases p u , and thus decreases w pe .
– if x e > 0 then we know that vu is in the residual graph and ineligible. Since vu is
ineligible, w pe must be greater than 0. Condition (B1) still holds because w pe can only
decrease until it is at most 0 and vu becomes eligible.
– if x e = 0 then condition (B2) still holds because w pe decreases.

Note that at the beginning of the algorithm, x e = 0 and w pe = w e − le w max ≤ 0 for each edge
e. Therefore, the invariants (B2) holds. Induction then gives that these invariants hold throughout
the course of the algorithm.

3.3

Bounding Weights of Paths

We can now turn our attention to the approximation factor. The main difficulty in this proof
is due to cancellations of flows pushed at previous scales. Our proof relies on performing a path
decomposition on each blocking flow in the history of the final solution x . We will view the final
flow, x , as a sum of flows from the collection P.
X
x =
xP.
P ∈P

Note here that x P is a quantity that specifies the amount of flow on that path. We also define FP
to be the set of edges going forward on P , and BP to be the set of edges going backward on P . We
use this decomposition to map backward flow to forward flow in an earlier scale. We will also use
scale(P ) to denote the scale at which P was pushed, and δP to denote δscale(P ) .
Note that we will likely push flows on an edge in forward and backward directions many times
throughout the course of the algorithm. Each of these instances belong to a different path, and is
taken care of separately in the summation. We first establish a lower bound on the weight of each
path using the eligibility criteria: we show that the weight of the path routed at phase i can be
lower bounded by terms involving δi , the step size at that phase.
12

Lemma 3.7.

X

e∈FP

we −

X

e∈BP

we ≥

DδP
2ǫ

Proof. Let p be the vertex potentials from when flow was pushed along P . Note that p may not
be the final potentials. By the definition of w pe , we have
X
X
X
X
we −
we =
w pe −
w pe + (p t − p s ) .
e∈FP

e∈BP

e∈FP

e∈BP

For the edges on the path, the eligibility rules give
• w pe ≥ δP ≥ 0 if e ∈ FP , and
• −w pe ≥ 0 if e ∈ BP .
Furthermore, our outer loop condition on Line 2a ensures that at scale i, p t is at least Dw max /2i+1 =
Dδi /2ǫ, while p s is always 0. Therefore the total is at least Dδi /2ǫ.
This allows us to map the final inaccuracies of weights caused by the Condition (B2) of the
invariants to ǫ of the total weights. The following proof hinges on path decompositions
Lemma 3.8. Let x be the final answer. Then we have
X
X
w ex e.
3le δef x e ≤ 6ǫ
e

e

Proof. Let x P be the amount of flow sent through P. The definition of x and summation of flows
gives
X
X
xe =
xP −
xP.
P :e∈FP

P :e∈BP

reversing the ordering of summation, and aggregating per edge gives:


X
X
X
X
3le δef x e =
3le δef 
xP −
xP.
e

e

P :e∈FP

P :e∈BP

For each edge e,



δef 

X

P :e∈FP

xP −

X

P :e∈BP



xP =

X

P :e∈FP

δef x P −

X

δef x P

(1)

P :e∈BP

Consider the set of paths P1 , . . . Pk sending flow on edge e (in both directions) in the order of index
i for i = 1 . . . k. Whenever a flow is sent from v to u (a backward direction), there must be some
existing flow from u to v. By breaking a path into multiple paths carrying smaller amounts of flow,
we may assume that for each Pi such that e ∈ BPi , there exists Pj such that j < i, e ∈ FPj and
x Pi = x Pj . We define a function that maps i to j. Since j < i, we must have δPj ≥ δPi . It follows
that
δef x Pj − δef x Pi = 0 ≤ δPj x Pj − δPi x Pi
13

We apply the following modifications to the RHS of equation (1). For each pair (i, j) such that i
is mapped to j, we increase the multiplication factor of x Pi from δef to δPi and the multiplication
factor of x Pj from δef to δPj . Finally, for the remaining forward flows that are not canceled, we
increase δef to the value δP of the path containing them. Such modifications can only increase the
value of the RHS of (1). Therefore, for each edge e,
X

P :e∈FP

δef x P −

X

P :e∈BP

δef x P ≤

X

P :e∈FP

δP x P −

X

δP x P .

P :e∈BP

Plugging back to the summation, we have


X
X
X
X
3le δef x e ≤
3le 
δP x P −
δP x P  .
e

e

P :e∈FP

P :e∈BP

Changing the order of summation and notice that for each path P
X
X
le δP −
le δP = DδP ,
e∈FP

which by Lemma 3.7 is bounded by 2ǫ
then gives the result.

3.4

e∈BP

P

e∈FP

we −

P

e∈BP


w e . Summing over all paths P ∈ P

Putting Things Together

It remains to put these together through the use of reduced costs in a way analogous to Lemma 2.5.
Proof. (of Theorem 3.1) The number of iterations in each scale is D/2ǫ + 2D = O(D/ǫ). The
number of scales is log(w max /w min ). Each iteration takes O(m log n) to find a blocking flow.
Therefore, the total running time is O ((Dm log n/ǫ) log(w max /w min )).
∗
For the approximation guarantees,
any
pP
denote the final potenP consider
P optimal flow
Px . pLet
p
tials. Once again, Lemma 2.1 gives e w e x e = e w e x e and e w e x ∗e = e w e x ∗e .
We will incorporate the invariants from Figure 7 through two cases:
1. If x e < x ∗e , then x e < c e , and the invariant gives w pe ≤ 2δT , which implies
w pe x e ≥ (w pe − 2δT ) x e ≥ (w pe − 2δT ) x ∗e .
Since δT = ǫw min ≤ w e , this implies
x e w pe ≥ x ∗e w pe − 2ǫw e x ∗e .
2. If x e > x ∗e , then x e > 0, and the invariant gives
w pe ≥ −3le δef
which combined with x ∗e ≤ x e gives:




x e w pe + 3le δef ≥ x ∗e w pe + 3le δef ≥ x ∗e w pe
14

Combining these gives
X
e


 X 

x e w pe + 3le δef
x e w e + 3le δef =
e

≥

X
e

x ∗e w pe − 2ǫ

= (1 − 2ǫ)

X

X

w e x ∗e

e

w e x ∗e

e

and the result then follows from Lemma 3.8.

4

Non-Linear Networks

We now move to the non-linear setting with arbitrary capacities. The primal objective becomes:
X
max
fe (x e )
e

Here we will let w e (x e ) denote the weight of e when x e units are on it, i.e.,
w e (x e ) =

d
fe (x e ).
dx e

Since fe (·) is concave, we know that w e (x e ) is monotonically decreasing. Pseudocode of our
algorithm is in Figure 8, and its eligibility rules are in Figure 9. Note that the eligibility rules in
the pseudocode is a shorter version of the one in Figure 9.
We remark that the cost of finding Le and Ue , the maximum amount the flow can increase/decrease
before the gradient of fe (x e ) changes by ∆, depends on the structures of fe (·). In case of simple
functions such as quadratics, they can be calculated in closed form. For more complex functions,
finding these points can be viewed as analogs of line searches [BV04].
Conceptually, we divide each edge uv into multiple imaginary parallel edges between u and v,
each with a linear weight function. This can be viewed as approximating w e (x e ) by a decreasing
step function. To be precise, for each edge e, we break it into k parallel edges e1 , . . . , ek such that:
1. w e1 = ⌊w e (0)/δT ⌋δT , w ek = ⌊w e (c e )/δT ⌋δT and w ei = w ei−1 − δT for all 1 < i < k.
2. c ei = x i − x i−1 where x i s are such that x 0 = 0, x k = c e and w e (x i ) = w ei for all 0 < i < k.
Let G = (V, E) be the original network, and G = (V, E) be the network with multiedges. We say
that a flow x in G is well-ordered if the following condition holds for every e:
x ei > 0 ⇒ x ej = c ej

∀j < i.

A flow x in G is equivalent with a flow x in G if:
X
x ej = x e .
j

Notice that the well-ordered property ensures that there is a unique reverse mapping from x e to
x e1 . . . x ek as well.
15

x = ConcaveFlow (G, s, t, {c e , fe } , w min , w max , ǫ)
Input: DAG G from s to t,
capacities c e and concave weight functions fe along each edge e,
bounds w min and w max s.t. w min ≤ dxd e fe (x e ) ≤ w max ∀ 0 ≤ x e ≤ c e , error tolerance ǫ.
Output: (1 − ǫ) approximate maximum weight flow x .
1. Compute levels lu of the vertices u (length of a longest path from s to u).
Initialize δ(0) = ǫw max , p u = w max · lu , x e = 0.
max
2. For i from 1 to T = log w
w min :

(a) Repeat until p t =

Dw max
2i+1

if i < T or until p t = 0 if i = T :

i. Form eligibility graph from all arcs with positive capacities given by:
A. Forward (u → v): max ∆ s.t. x e + ∆ ≤ c e and p u − p v + dxd e fe (x e + ∆) ≥ δi .

B. Backward (v → u): max ∆ s.t. ∆ ≤ x e and p u − p v + dxd e fe (x e − ∆) ≤ 0.
ii. Augmentation: Send a blocking flow in the eligible graph.
iii. Dual Adjustment: Recompute the eligible graph, for each vertex u unreachable
from s, set p u ← p u − δi .

(b) If i < T :

i. Dual Rescale: p u ← p u + δi lu ,
ii. δi+1 ← δ2i .
Figure 8: Algorithm for Concave Networks
Lemma 4.1. Let (x , p) be a flow-potential pair at some point in the course of ConcaveFlow on
input G. ScalingFlow on input G can maintain a flow-potential pair (x , p) such that:
1. x is well-ordered.
2. x and x are equivalent.
Proof. It suffices to prove that the above claim holds in an Eligibility Labeling and an Augmentation
step.
Consider an edge uv that is eligible in forward direction in ConcaveFlow algorithm. Since
x is well-ordered and equivalent to x , there are some eligible multiedges between u and v in
ScalingFlow. Moreover, the first condition in Figure 9 guarantees that the amount of flow
allowed on uv is equal to sum of capacities of all eligible parallel edges from u to v in the multiedges
setting. This follows because
1. The value of w e (x e + ∆) such that w pe (x e + ∆) = δi is a multiple of δi , since p u and p v are
also multiples of δi assuming ǫ is a power of 2.
2. A weight of each edge in G is a multiple of δT by construction.

16

1. Forward edge: if x e < c e , uv is eligible if δi < w pe (x e ), and can has forward capacity
Ue (x e , i) := min {c e − x e , ∆ such that w pe (x e + ∆) = δi } .
2. Backward edge: if x e > 0, vu is eligible if 0 > w pe (x e ), with capacity
Le (x e , i) := min {x e , ∆ such that w pe (x e − ∆) = 0} .
Figure 9: Eligiblity Rules for Scaling Algorithm for Concave Weight Functions.
A similar argument can be applied to the backward eligibility case. Specifically, the amount of
flow that can be pushed back on uv in ConcaveFlow is equal to sum of capacities of all eligible
multiedges from v to u in ScalingFlow.
It follows that a blocking flow in the eligible graph in ConcaveFlow is also a blocking flow
in the eligible graph in ScalingFlow. Given a blocking flow z in the single-edge setting, we
can distribute z uv among eligible multiedges between u and v such that the resulting flow x in
ScalingFlow is still well-order, and still equivalent to the resulting flow x in ConcaveFlow.
This mapping then allows us to bound the result of the continuous process, leading to our main
result.
Proof. (Of Theorem 1.1)
Let x ∗ be the optimal solution in the concave flow problem in G, and x be the final solution
returned by ConcaveFlow. Let x ∗ be a solution in G such that x ∗ is well-ordered and equivalent
to x ∗ . By Lemma 4.1, ScalingFlow on input G can produce a solution x in such that x is
well-ordered and equivalent to x . At the end of the algorithm, the invariant in Section 3 must hold
for the solution x . By Theorem 3.1,
X
X
w e x e ≥ (1 − 8ǫ)
w e x ∗e .
e∈G

e∈G

Since x is equivalent to x and the step function defined by {w ei , c ei } is always below the function
w e,
Z xe
X
w e (t)dt ≥
fe (x e ) =
w ex e.
0

e∈G

Notice that the step function defined by {w ei + δT , c ei }, however, is always above the function w e .
Since x ∗ is equivalent to x ∗ ,
Z x ∗e
X
∗
(w e + δT ) x e ≥
w e (t)dt = fe (x ∗e ).
0

e∈G

Since δT = ǫw min ≤ ǫw e for all e ∈ G, we have w e + δT ≤ w e (1 + ǫ). It follows that
X
w e x ∗e ≥ fe (x ∗e ).
(1 + ǫ)
e∈G

17

Putting everything together,
fe (x e ) ≥
≥

X

e∈G

w e x e ≥ (1 − 8ǫ)

X

w e x ∗e

e∈G

1 − 8ǫ
fe (x ∗e ) ≥ (1 − 9ǫ)fe (x ∗e ).
1+ǫ

Finally, by applying a similar argument as in Theorem3.1, it is easy to see that the running time
of ConcaveFlow is O Dmǫ−1 log(w max /w min ) log n .

5

Discussion

We extended the Duan-Pettie framework for approximating weighted matchings [DP14] to flows on
small depth networks [Coh95]. Our approach can be viewed as viewing the length of augmenting
paths as a regularizing parameter on the weights of augmenting paths. For general concave weight
functions, the routine can also be viewed as a dynamical system that adjusts flows based on the
gradient of the current weight functions [BMV12, BBD+ 13, SV16]. Also, we believe our approach
can be parallelized, and extends to non-bipartite graphs: here the challenge is mostly with finding
an approximate extension of blocking flow routines.
Another related application with small depth networks is finding high density subgraphs in
networks [GT15, MPP+ 15, BHNT15]. These problems can be solved using parameteric maximum
flows or binary searching over maximum flows [Gol84]. In both of these cases, the networks have
constant depth, but the reductions also change the notions of approximation. Weights represents
an additional tool in such routines, and we plan to further investigate its applications.

References
[AG14]

Kook Jin Ahn and Sudipto Guha. Near linear time approximation schemes for uncapacitated and capacitated b-matching problems in nonbipartite graphs. In Proceedings
of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’14,
pages 239–258, 2014. Available at: https://arxiv.org/abs/1307.4355.

[AMO93]

Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory,
Algorithms, and Applications. Prentice Hall, Englewood Cliffs, NJ, 1993.

[AMOR95] Ravindra K Ahuja, Thomas L Magnanti, James B Orlin, and MR Reddy. Applications of network optimization. Handbooks in Operations Research and Management
Science, 7:1–83, 1995. Available at: http://jorlin.scripts.mit.edu/docs/publications/52applications%20of%20network.pdf.
[BBD+ 13] Luca Becchetti, Vincenzo Bonifaci, Michael Dirnberger, Andreas Karrenbauer,
and Kurt Mehlhorn.
Physarum can compute shortest paths: Convergence
proofs and complexity bounds.
In Automata, Languages, and Programming
- 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013,
Proceedings, Part II, pages 472–483, 2013.
Available at https://people.mpiinf.mpg.de/˜mtd/files/physarum shortest path.pdf.

18

[BHNT15] Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos
Tsourakakis. Space-and time-efficient algorithm for maintaining dense subgraphs on
one-pass dynamic streams. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 173–182. ACM, 2015.
[BMV12]

Vincenzo Bonifaci, Kurt Mehlhorn, and Girish Varma. Physarum can compute shortest
paths. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 233–240, 2012.
Available at http://arxiv.org/abs/1106.0423.

[BV04]

S. Boyd and L. Vandenberghe. Convex Optimization. Camebridge University Press,
2004. Available at https://web.stanford.edu/˜boyd/cvxbook/bv cvxbook.pdf.

[CKM+ 11] Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and
Shang-Hua Teng. Electrical flows, Laplacian systems, and faster approximation of
maximum flow in undirected graphs. In Proceedings of the 43rd ACM Symposium on
Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 273–282,
2011. Available at http://arxiv.org/abs/1010.2921.
[Coh95]

Edith Cohen. Approximate max-flow on small depth networks. SIAM J. Comput.,
24(3):579–597, June 1995.

[DJ12]

N. Devanur and K. Jain. Online matching with concave returns. In Proceedings of the
44th ACM Symposium on Theory of Computing, STOC, 2012.

[DP14]

Ran Duan and Seth Pettie. Linear-time approximation for maximum weight matching.
Journal of the ACM (JACM), 61(1):1, 2014.

[Gab17]

Harold N. Gabow. The weighted matching approach to maximum cardinality matching.
CoRR, abs/1703.03998, 2017. Available at: http://arxiv.org/abs/1703.03998.

[Gol84]

A. V. Goldberg. Finding a maximum density subgraph. Technical report, Berkeley,
CA, USA, 1984.

[GR98]

Andrew V. Goldberg and Satish Rao. Beyond the flow decomposition barrier. J. ACM,
45:783–797, September 1998.

[GT87]

Andrew V. Goldberg and Robert Endre Tarjan. Solving minimum-cost flow problems
by successive approximation. In Proceedings of the nineteenth annual ACM symposium
on Theory of computing, 1987.

[GT89]

Harold N. Gabow and Robert Endre Tarjan. Faster scaling algorithms for network
problems. SIAM J. Comput., 18(5):1013–1036, 1989.

[GT91]

Harold N. Gabow and Robert Endre Tarjan. Faster scaling algorithms for general
graph-matching problems. J. ACM, 38(4):815–853, 1991.

[GT15]

Aristides Gionis and Charalampos E. Tsourakakis. Dense subgraph discovery: Kdd
2015 tutorial. In Proceedings of the 21th ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, KDD ’15, pages 2313–2314, New York, NY,
USA, 2015. ACM.
19

[Hoc07]

Dorit S Hochbaum. Complexity and algorithms for nonlinear optimization problems.
Annals of Operations Research, 153(1):257–296, 2007.

[Kar72]

Richard M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W.
Thatcher, editors, Complexity of Computer Computations, pages 85–103. Plenum Press,
1972.

[KMVV15] Ravi Kumar, Benjamin Moseley, Sergei Vassilvitskii, and Andrea Vattani. Fast greedy
algorithms in mapreduce and streaming. ACM Transactions on Parallel Computing,
2(3):14, 2015.
[LMSV11] Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering:
a method for solving graph problems in mapreduce. In Proceedings of the twenty-third
annual ACM symposium on Parallelism in algorithms and architectures, pages 85–94.
ACM, 2011.
[LS14]

Yin Tat Lee and Aaron Sidford.
Path finding methods for linear programming: Solv√
ing linear programs in Õ( rank) iterations and faster algorithms for maximum flow.
In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium
on, pages 424–433. IEEE, 2014. Available at http://arxiv.org/abs/1312.6677 and
http://arxiv.org/abs/1312.6713.

[Mad13]

Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual
Symposium on, pages 253–262. IEEE, 2013.

[MAG+ 13] Faraz Makari Manshadi, Baruch Awerbuch, Rainer Gemulla, Rohit Khandekar, Julián
Mestre, and Mauro Sozio. A distributed algorithm for large-scale generalized matching.
Proceedings of the VLDB Endowment, 6(9):613–624, 2013.
[MPP+ 15] Michael Mitzenmacher, Jakub Pachocki, Richard Peng, Charalampos Tsourakakis, and
Shen Chen Xu. Scalable large near-clique detection in large-scale networks via sampling. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining, pages 815–824. ACM, 2015.
[Orl93]

James B Orlin. A faster strongly polynomial minimum cost flow algorithm. Operations
research, 41(2):338–350, 1993.

[Orl13]

James B Orlin. Max flows in o(nm) time, or better. In Proceedings of the forty-fifth
annual ACM symposium on Theory of computing, pages 765–774. ACM, 2013.

[Pen16]

Richard Peng. Approximate undirected maximum flows in o (m polylog (n)) time. In
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1862–1867. SIAM, 2016. Available at http://arxiv.org/abs/1411.7631.

[Sch03]

A. Schrijver. Combinatorial Optimization. Springer-Verlag, 2003.

[ST83]

Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J.
Comput. Syst. Sci., 26(3):362–391, June 1983.

20

[SV16]

Damian Straszak and Nisheeth K. Vishnoi. Natural algorithms for flow problems. In
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1868–1883,
2016.

[TTL+ 12] Wenbin Tang, Jie Tang, Tao Lei, Chenhao Tan, Bo Gao, and Tian Li. On optimization
of expertise matching with various constraints. Neurocomputing, 76(1):71–83, 2012.
[Vég12]

László A Végh. Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. In Proceedings of the forty-fourth annual ACM
symposium on Theory of computing, pages 27–40. ACM, 2012.

[VVS10]

Erik Vee, Sergei Vassilvitskii, and Jayavel Shanmugasundaram. Optimal online assignment with forecasts. In Proceedings of the 11th ACM conference on Electronic
commerce, pages 109–118. ACM, 2010.

[WRM15] Di Wang, Satish Rao, and Michael W. Mahoney. Unified acceleration method for
packing and covering problems via diameter reduction. CoRR, abs/1508.02439, 2015.
[ZO15]

A

Zeyuan Allen Zhu and Lorenzo Orecchia. Nearly-linear time positive LP solver with
faster convergence rate. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015,
pages 229–236, 2015.

Applications

We now outline some concrete applications of our formulation on small depth networks: many of
them are discussed in more details in the survey by Ahuja et al. [AMOR95].

A.1

Assignment Problems

Our techniques are directly motivated by those developed for approximate max weight matchings [DP14]. This problem, when phrased as the assignment problem, has applications in matching
objects across snapshots as well as direct uses in assignment indicated by its name. Names of some
of these applications, as enumerated in Application 16-18 of [AMOR95], include locating objects
in space, matching moving objects, and rewiring typewriters.
The problem of finding matchings in large scale graphs has received much attention in experimental algorithm design [LMSV11, MAG+ 13, KMVV15]. These instances often involve capacities
on both sides, as well as edges in between. They are related to b-matchings, and have been studied
as generalized matchings. Previous works that incorporated concave costs include:
• [VVS10] studied Adwords matching using concave objective functions, and showed several
stability and robustness properties of these formulations.
• [TTL+ 12] utilized concave networks to perform assignments of experts to queries with additional constraints on groups of experts as well as queries. This leads to a depth 4 network
with 3 layers corresponding to node groups respectively.

21

• [DJ12] considered a generalization of the well-known Adwords problem, which asks for maximizing the sum of budgeted linear functions of agents. In the generalization, the utility of
each agents is a concave function (of her choice) of her total allocation. The objective is to
maximize the sum of budgeted utilities, and an optimal online algorithm is given for this
generalization.
Another instance of concave cost matching is matrix balancing (Application 28 in [AMOR95]):
given a fractional matrix, we would like to find a matrix with a specified row /column sum while
minimizing distance under some norm. Here a bipartite network can be constructed by turning
the rows into left vertices, columns into right vertices. The concave functions can then go onto the
edges as costs.
Our algorithm is able to handle such generalizations, and lead to bounds similar to those from
recent improvements to positive packing linear programs [ZO15].
Generalizations of matching and assignment lead naturally to small depth networks. One such
generalization is 3-Dimensional matching which is NP-hard [Kar72]. Here the generalization of
edges is 3-tuples of the form (x, y, z), with one element each from sets X, Y , and Z, and 3dimensional matching asks for the maximum weighted set of tuples that uses each element in X,
Y , and Z at most once.
A restriction of this problem on the other hand is in P : the set of acceptable tuples are given
by pairs of edges between XY and Y Z. Specifically, a tuple (x, y, z) can be used iff xy ∈ EXY
and yz ∈ EY Z , and its cost is given by the sum of the two edges. This version can be solved by
maximum cost flow on a depth 5 network:
• For each element x, y or z, create an in and out vertex, connected by an edge with unit
capacity.
• Connect Xout to Yin and Yout to Zin with edges corresponding to EXY and EY Z .
• Connect s to Xin and Zout to t.

A.2

Mincost Flow

Minimum cost flow asks to minimize the cost instead of maximizing it. This is perhaps the most
well-known formulation of our problem. However, it doesn’t tolerate approximations very well: if
we stay with non-negative costs, we need to specify the amount of flow. If this is done exactly, it
becomes flow feasiblity on a small depth network. There are known reductions of directed maximum
flows to this instance (e.g. [Mad13], Section 3).
One way to limit the total amount of flow is to associate a reward with each unit sent from s
to t. Specifically, let q e > 0 be the cost of one unit of flow on e, and Q > 0 be the reward of one
unit sent from s to t, the objective function is
X
min
q e x e − Qf
e

where f is the total amount of flow from s to t. In this case, negating the cost brings us back to
the maximum weight flow problem. The approximation factor on the other hand becomes additive:

22

Lemma A.1. Let (x ∗ , f ∗ ) be the optimal solution to the above mincost flow problem, The algorithm
ScalingFlow in Section 3 gives a solution (x , f ) such that:
!
X
X
q e x ∗e − Qf ∗ + 2ǫQf ∗
q e x e − Qf ≤ (1 + ǫ)
e

e

A proof of Lemma A.1 can be found in Appendix B. Applications of minimum cost flows that
lead to small depth networks include:
• Job scheduling, or optimal loading of a hopping airplane (application 13 from [AMOR95]):
When phrased as scheduling, this can be viewed as completing a maximum set of jobs each
taking place between days [si , ti ] and giving gain ci so that at no point more than ui jobs are
being done simultaneously on day i.
This can be solved with a maximum cost flow whose depth is the number of days:
– The days become a path, with capacity ui ,
– For each job, create a node (connected to source with capacity 1) with two edges, one
with cost 0 to ti , and one with cost ci to si .
– Each node on the path has an edge to sink, t, with capacity equalling the number of
jobs ending that day.
This leads to a network whose depth is the number of days, or number of stops. Both of these
quantities are small in real instances.
• Balancing of schools (Application 15 from [AMOR95]): the goal is to assign students from
varying backgrounds to schools, belong to several districts, so that each school as well as each
district has students with balanced backgrounds. Furthermore, the cost corresponds to the
distance the student needs to travel to the schools. This leads to a depth 3 network where
the layers are the students, schools, and districts respectively.
Finally, we believe several applications can benefit from the incorporation of non-linear weight
functions. As an instance, we can solve the following problem using our framework: Let G be a
network with k sources, {si , 1 ≤ P
i ≤ k}, and a sink, t, and let fi be a concave function for each
1 ≤ i ≤ k. We wish to maximize i fi (Fi ), where Fi is the amount of flow sent from si to t.

B

Negative Weight Functions

We consider the case where our network can have negative weights. For simplicity, we only study
linear weight functions. The analysis, however, can be extended to the case of concave function as
in Section 4. Here, we assume that the absolute values of the weights are bounded:
w max ≥ |w e | ≥ w min

∀e.

Lemma B.1. Let x be a solution returned by ScalingFlow, and let x ∗ be the optimal solution
X
X
X
w e x e ≥ (1 − 8ǫ)
w e x ∗e + (1 + 8ǫ)
w e x ∗e .
e

w e >0

w e <0

23

Proof. A key observation is that the Lemmas 3.7 and 3.8 are robust under negative weights. Using
an argument similar to as in Theorem 3.1, we have:
1. If x e < x ∗e , then x e < c e , and the invariant gives w pe ≤ 2δT , which implies
w pe x e ≥ (w pe − 2δT ) x e ≥ (w pe − 2δT ) x ∗e .
Since δ(T ) ≤ ǫw min ≤ ǫ|w e | for all e, we consider 2 cases:
(
w pe x ∗e − 2ǫw e x ∗e
w pe x e ≥ (w pe − 2δT ) x ∗e ≥
w pe x ∗e + 2ǫw e x ∗e

if w e > 0,
if w e < 0.

2. If x e > x ∗e , then x e > 0, and the invariant gives w pe ≥ −3le δef , which combined with x ∗e ≤ x e
gives:




x e w pe + 3le δef ≥ x ∗e w pe + 3le δef ≥ x ∗e w pe

Combining these then gives

 X 
X 
x e w pe + 3le δef
x e w e + 3le δef =
e

e

≥

≥

X
e

w pe x ∗e −

X

e:w e >0

X

2ǫw e x ∗e +

e:w e <0

= (1 − 2ǫ)

w e x ∗e

e:w e >0

2ǫw e x ∗e

e:w e <0

(w e x ∗e − 2ǫw e x ∗e ) +
X

X

X

(w e x ∗e + 2ǫw e x ∗e )

e:w e <0

+ (1 + 2ǫ)

X

w e x ∗e

e:w e <0

and the result then follows from Lemma 3.8.
Proof. (Of Lemma A.1) Let w e = −q e for every e, and add a directed edge from t to a dummy
vertex t′ with w tt′ = Q. By Lemma B.1, a solution returned by ScalingFlow on that instance
has the following guarantee:
X
X
Qf −
q e x e ≥ (1 − ǫ)Qf ∗ − (1 + ǫ)
q e x ∗e .
e

Negating both sides gives
X
e

q e x e − Qf ≤ (1 + ǫ)
= (1 + ǫ)

X

q e x ∗e − (1 − ǫ)Qf ∗

X

24


q e x ∗e − Qf ∗ + 2ǫQf ∗ .

