CS 577 - Network Flow
Marc Renault
Department of Computer Sciences
University of Wisconsin – Madison
Spring 2021
TopHat Join Code: 524741
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Network Flow
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Network Flow
Flow Problems
Flow Network / Transportation Networks: Connected
directed graph with water flowing / traffic moving
through it.
Edges have limited capacities.
Nodes act as switches directing the flow.
Many, many problems can be cast as flow problems.
Ford-Fulkerson Method (1956)
L R Ford Jr.
D. R. Fulkerson
1/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Network Flow
Flow Problems
Flow Network / Transportation Networks: Connected
directed graph with water flowing / traffic moving
through it.
Edges have limited capacities.
Nodes act as switches directing the flow.
Many, many problems can be cast as flow problems.
Ford-Fulkerson Method (1956)
L R Ford Jr.
D. R. Fulkerson 1/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Flow Network
t
u
s
v
10
10
30
20
20
Basic Flow Network
Directed graph G = (V,E).
Each edge e has ce ≥ 0.
Source s ∈ V and sink t ∈ V.
Internal node V/{s, t}.
Defining Flow
Flow starts at s and exits at t.
Flow function: f : E→ R+; f (e) is the flow across edge e.
Flow Conditions:
i Capacity: For each e ∈ E, 0 ≤ f (e) ≤ ce.
ii Conservation: For each v ∈ V/{s, t},∑
e into v
f (e) = f in(v) = f out(v) =
∑
e out of v
f (e)
Flow value v(f ) = f out(s) = f in(t)
2/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Flow Network
t
u
s
v
10
10
30
20
20
Basic Flow Network
Directed graph G = (V,E).
Each edge e has ce ≥ 0.
Source s ∈ V and sink t ∈ V.
Internal node V/{s, t}.
Defining Flow
Flow starts at s and exits at t.
Flow function: f : E→ R+; f (e) is the flow across edge e.
Flow Conditions:
i Capacity: For each e ∈ E, 0 ≤ f (e) ≤ ce.
ii Conservation: For each v ∈ V/{s, t},∑
e into v
f (e) = f in(v) = f out(v) =
∑
e out of v
f (e)
Flow value v(f ) = f out(s) = f in(t)
2/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Flow Network
t
u
s
v
10
10
30
20
20
Basic Flow Network
Directed graph G = (V,E).
Each edge e has ce ≥ 0.
Source s ∈ V and sink t ∈ V.
Internal node V/{s, t}.
Defining Flow
Flow starts at s and exits at t.
Flow function: f : E→ R+; f (e) is the flow across edge e.
Flow Conditions:
i Capacity: For each e ∈ E, 0 ≤ f (e) ≤ ce.
ii Conservation: For each v ∈ V/{s, t},∑
e into v
f (e) = f in(v) = f out(v) =
∑
e out of v
f (e)
Flow value v(f ) = f out(s) = f in(t)
2/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Flow Network
t
u
s
v
10
10
30
20
20
Basic Flow Network
Directed graph G = (V,E).
Each edge e has ce ≥ 0.
Source s ∈ V and sink t ∈ V.
Internal node V/{s, t}.
Defining Flow
Flow starts at s and exits at t.
Flow function: f : E→ R+; f (e) is the flow across edge e.
Flow Conditions:
i Capacity: For each e ∈ E, 0 ≤ f (e) ≤ ce.
ii Conservation: For each v ∈ V/{s, t},∑
e into v
f (e) = f in(v) = f out(v) =
∑
e out of v
f (e)
Flow value v(f ) = f out(s) = f in(t)
2/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Flow Network
t
u
s
v
10
10
30
20
20
Basic Flow Network
Directed graph G = (V,E).
Each edge e has ce ≥ 0.
Source s ∈ V and sink t ∈ V.
Internal node V/{s, t}.
Defining Flow
Flow starts at s and exits at t.
Flow function: f : E→ R+; f (e) is the flow across edge e.
Flow Conditions:
i Capacity: For each e ∈ E, 0 ≤ f (e) ≤ ce.
ii Conservation: For each v ∈ V/{s, t},∑
e into v
f (e) = f in(v) = f out(v) =
∑
e out of v
f (e)
Flow value v(f ) = f out(s) = f in(t)
2/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Maximum-Flow Problem
t
u
s
v
10
10
30
20
20
Max-Flow
Given a flow network G, what is the
maximum flow value, i.e., what is the
flow f that maximizes v(f )?
Alternate View: Min-Cut
A Cut: Partition of V into sets (A,B) with s ∈ A and t ∈ B.
Flow from s to t must cross the set A to B.
Cut capacity: c(A,B) = ∑e out of A ce
Minimum-cut of G: The cut (A∗,B∗) that minimizes
c(A∗,B∗) for G.
The min-cut and max-flow are the same value for any flow
network.
3/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Maximum-Flow Problem
t
u
s
v
10
10
30
20
20
Max-Flow
Given a flow network G, what is the
maximum flow value, i.e., what is the
flow f that maximizes v(f )?
Alternate View: Min-Cut
A Cut: Partition of V into sets (A,B) with s ∈ A and t ∈ B.
Flow from s to t must cross the set A to B.
Cut capacity: c(A,B) = ∑e out of A ce
Minimum-cut of G: The cut (A∗,B∗) that minimizes
c(A∗,B∗) for G.
The min-cut and max-flow are the same value for any flow
network.
3/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Maximum-Flow Problem
t
u
s
v
10
10
30
20
20
Max-Flow
Given a flow network G, what is the
maximum flow value, i.e., what is the
flow f that maximizes v(f )?
Alternate View: Min-Cut
A Cut: Partition of V into sets (A,B) with s ∈ A and t ∈ B.
Flow from s to t must cross the set A to B.
Cut capacity: c(A,B) = ∑e out of A ce
Minimum-cut of G: The cut (A∗,B∗) that minimizes
c(A∗,B∗) for G.
The min-cut and max-flow are the same value for any flow
network.
3/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Maximum-Flow Problem
t
u
s
v
10
10
30
20
20
Max-Flow
Given a flow network G, what is the
maximum flow value, i.e., what is the
flow f that maximizes v(f )?
Alternate View: Min-Cut
A Cut: Partition of V into sets (A,B) with s ∈ A and t ∈ B.
Flow from s to t must cross the set A to B.
Cut capacity: c(A,B) = ∑e out of A ce
Minimum-cut of G: The cut (A∗,B∗) that minimizes
c(A∗,B∗) for G.
The min-cut and max-flow are the same value for any flow
network.
3/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Maximum-Flow Problem
t
u
s
v
10
10
30
20
20
Max-Flow
Given a flow network G, what is the
maximum flow value, i.e., what is the
flow f that maximizes v(f )?
Alternate View: Min-Cut
A Cut: Partition of V into sets (A,B) with s ∈ A and t ∈ B.
Flow from s to t must cross the set A to B.
Cut capacity: c(A,B) = ∑e out of A ce
Minimum-cut of G: The cut (A∗,B∗) that minimizes
c(A∗,B∗) for G.
The min-cut and max-flow are the same value for any flow
network.
3/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Maximum-Flow Problem
t
u
s
v
10
10
30
20
20
Max-Flow
Given a flow network G, what is the
maximum flow value, i.e., what is the
flow f that maximizes v(f )?
Alternate View: Min-Cut
A Cut: Partition of V into sets (A,B) with s ∈ A and t ∈ B.
Flow from s to t must cross the set A to B.
Cut capacity: c(A,B) = ∑e out of A ce
Minimum-cut of G: The cut (A∗,B∗) that minimizes
c(A∗,B∗) for G.
The min-cut and max-flow are the same value for any flow
network.
3/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Designing the Approach
t
u
s
v
10
10
30
20
20
TopHat 1
What is the max-flow value in the
example?
4/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Designing the Approach
t
u
s
v
10
10
30
20
20
TopHat 2
What is the min-cut value in the
example?
4/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Designing the Approach
t
u
s
v
10
10
30
20
20
t
u
s
v
10/0
10/0
30/20
20/20
20/20
Basic Greedy Approach
Initialize f (e) = 0 for all edges.
While there is a path from s to t with available capacity,
push flow equal to the minimum available capacity along
path.
We need a mechanism to reverse flow...
4/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Designing the Approach
t
u
s
v
10
10
30
20
20
t
u
s
v
10/0
10/0
30/20
20/20
20/20
Basic Greedy Approach
Initialize f (e) = 0 for all edges.
While there is a path from s to t with available capacity,
push flow equal to the minimum available capacity along
path.
We need a mechanism to reverse flow...
4/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Residual Graph
t
u
s
v
10
10
30
20
20
t
u
s
v
10
10
1020
20
20
Residual Graph
Given a flow network G and a flow f on G, we get the residual
graph Gf :
Same nodes as G.
For edge (u, v) in E:
Add edge (u, v) with capacity ce − f (e).
Add edge (v,u) with capacity f (e).
5/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Residual Graph
t
u
s
v
10
10
30
20
20
t
u
s
v
10
10
1020
20
20
Residual Graph
Given a flow network G and a flow f on G, we get the residual
graph Gf :
Same nodes as G.
For edge (u, v) in E:
Add edge (u, v) with capacity ce − f (e).
Add edge (v,u) with capacity f (e).
6/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Augmenting Path
t
u
s
v
10
10
30
20
20
t
u
s
v
10
20
10
10
20
20
Augmenting Path
A simple directed path from s to t.
bottleneck(P,Gf ): Minimum residual capacity on
augmenting path P.
7/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Augmenting Path
t
u
s
v
10
10
30
20
20
t
u
s
v
10
20
10
10
20
20
Augmenting Path
A simple directed path from s to t.
bottleneck(P,Gf ): Minimum residual capacity on
augmenting path P.
TopHat 3
List the nodes (separated by commas, i.e. s,u,t) of an
augmenting path in the example residual graph.
7/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Augmenting Path
t
u
s
v
10
10
30
20
20
t
u
s
v
10
20
10
10
20
20
Increasing the Flow along Augmenting Path
Push bottleneck(P,Gf ) = q along path P:
Pushing q along a directed edge in G, increase flow by q.
Pushing q in opposite directed of edge in G, decreases flow
by q.
7/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Augmenting Path
t
u
s
v
10
10
30
20
20
t
u
s
v
10
20
10
10
20
20
t
u
s
v
10
10
10
20
20
20
Increasing the Flow along Augmenting Path
Push bottleneck(P,Gf ) = q along path P:
Pushing q along a directed edge in G, increase flow by q.
Pushing q in opposite directed of edge in G, decreases flow
by q.
7/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Designing the Approach
t
u
s
v
10
10
30
20
20
t
u
s
v
10/0
10/0
30/20
20/20
20/20
Basic Greedy Approach
Initialize f (e) = 0 for all edges.
While there is a path from s to t with available capacity,
push flow equal to the minimum available capacity along
path.
We need a mechanism to reverse flow...
8/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Designing the Approach
t
u
s
v
10
10
30
20
20
t
u
s
v
10
20
10
10
20
20
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting path P:
Update flow f by bottleneck(P,Gf ) along P.
8/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Constant Increase and Termination
Observation 1
If all capacities are integers,
then all f (e), residual
capacities, and v(f ) are
integers at every iteration.
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
9/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Constant Increase and Termination
Observation 1
If all capacities are integers,
then all f (e), residual
capacities, and v(f ) are
integers at every iteration.
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
TopHat 4
What technique should we use to prove the observation?
9/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Constant Increase and Termination
Observation 1
If all capacities are integers,
then all f (e), residual
capacities, and v(f ) are
integers at every iteration.
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Lemma 1
v(f ′) > v(f ), where v(f ′) = v(f ) + bottleneck(P,Gf ) for an
augmenting path P in Gf .
9/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Constant Increase and Termination
Observation 1
If all capacities are integers,
then all f (e), residual
capacities, and v(f ) are
integers at every iteration.
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Lemma 1
v(f ′) > v(f ), where v(f ′) = v(f ) + bottleneck(P,Gf ) for an
augmenting path P in Gf .
Proof.
By definition of P, first edge of p is an out edge from s that we
increase by bottleneck(P,Gf ) = q. By the law of conservation,
this will give qmore flow.
9/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Constant Increase and Termination
Observation 1
If all capacities are integers,
then all f (e), residual
capacities, and v(f ) are
integers at every iteration.
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Lemma 1
v(f ′) > v(f ), where v(f ′) = v(f ) + bottleneck(P,Gf ) for an
augmenting path P in Gf .
Theorem 2
Let C = ∑e out of s ce, the FF method terminates in at most C
iterations.
9/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Constant Increase and Termination
Observation 1
If all capacities are integers,
then all f (e), residual
capacities, and v(f ) are
integers at every iteration.
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Lemma 1
v(f ′) > v(f ), where v(f ′) = v(f ) + bottleneck(P,Gf ) for an
augmenting path P in Gf .
Theorem 2
Let C = ∑e out of s ce, the FF method terminates in at most C
iterations.
Proof.
TopHat 5: What technique?
9/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Constant Increase and Termination
Observation 1
If all capacities are integers,
then all f (e), residual
capacities, and v(f ) are
integers at every iteration.
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Lemma 1
v(f ′) > v(f ), where v(f ′) = v(f ) + bottleneck(P,Gf ) for an
augmenting path P in Gf .
Theorem 2
Let C = ∑e out of s ce, the FF method terminates in at most C
iterations.
Proof.
From Lemma 1, the flow strictly increases at each iteration.
Hence, the residual capacity out of s decreases by at least 1 at
each iteration.
9/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Constant Increase and Termination
Observation 1
If all capacities are integers,
then all f (e), residual
capacities, and v(f ) are
integers at every iteration.
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Lemma 1
v(f ′) > v(f ), where v(f ′) = v(f ) + bottleneck(P,Gf ) for an
augmenting path P in Gf .
Theorem 2
Let C = ∑e out of s ce, the FF method terminates in at most C
iterations.
9/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Runtime
Observation 2
Since G is connected,
m ≥TH6.
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
10/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Runtime
Observation 2
Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
10/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Runtime
Observation 2
Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Theorem 3
Suppose all capacities are integers. Then, runtime of O(mC).
10/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Runtime
Observation 2
Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Theorem 3
Suppose all capacities are integers. Then, runtime of O(mC).
TopHat 7
Is this a polynomial bound?
No, it is pseudo-polynomial.
10/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Runtime
Observation 2
Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Theorem 3
Suppose all capacities are integers. Then, runtime of O(mC).
TopHat 7
Is this a polynomial bound? No, it is pseudo-polynomial.
10/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Runtime
Observation 2
Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Theorem 3
Suppose all capacities are integers. Then, runtime of O(mC).
Proof.
Theorem 2: termination happens in at most C iterations.
Work per iteration:
Overall: O(m)
1 Find an augmenting path:
2 Update flow along path P:
3 Build new Gf :
10/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Runtime
Observation 2
Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Theorem 3
Suppose all capacities are integers. Then, runtime of O(mC).
Proof.
Theorem 2: termination happens in at most C iterations.
Work per iteration:
Overall: O(m)
1 Find an augmenting path:
2 Update flow along path P:
3 Build new Gf :
10/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Runtime
Observation 2
Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Theorem 3
Suppose all capacities are integers. Then, runtime of O(mC).
Proof.
Theorem 2: termination happens in at most C iterations.
Work per iteration:
Overall: O(m)
1 Find an augmenting path: TH8: How can we do that?
2 Update flow along path P:
3 Build new Gf :
10/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Runtime
Observation 2
Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Theorem 3
Suppose all capacities are integers. Then, runtime of O(mC).
Proof.
Theorem 2: termination happens in at most C iterations.
Work per iteration:
Overall: O(m)
1 Find an augmenting path: BFS or DFS: O(m + n) .
2 Update flow along path P:
3 Build new Gf :
10/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Runtime
Observation 2
Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Theorem 3
Suppose all capacities are integers. Then, runtime of O(mC).
Proof.
Theorem 2: termination happens in at most C iterations.
Work per iteration:
Overall: O(m)
1 Find an augmenting path: BFS or DFS: O(m + n) .
2 Update flow along path P: TH9: Time bound?
3 Build new Gf :
10/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Runtime
Observation 2
Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Theorem 3
Suppose all capacities are integers. Then, runtime of O(mC).
Proof.
Theorem 2: termination happens in at most C iterations.
Work per iteration:
Overall: O(m)
1 Find an augmenting path: BFS or DFS: O(m + n) .
2 Update flow along path P: O(n).
3 Build new Gf :
10/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Runtime
Observation 2
Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Theorem 3
Suppose all capacities are integers. Then, runtime of O(mC).
Proof.
Theorem 2: termination happens in at most C iterations.
Work per iteration:
Overall: O(m)
1 Find an augmenting path: BFS or DFS: O(m + n) .
2 Update flow along path P: O(n).
3 Build new Gf : TH10: Time bound?
10/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Runtime
Observation 2
Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Theorem 3
Suppose all capacities are integers. Then, runtime of O(mC).
Proof.
Theorem 2: termination happens in at most C iterations.
Work per iteration:
Overall: O(m)
1 Find an augmenting path: BFS or DFS: O(m + n) .
2 Update flow along path P: O(n).
3 Build new Gf : O(m).
10/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Algorithm
Runtime
Observation 2
Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).
Refined Greedy Approach
Initialize f (e) = 0 for all edges.
While Gf contains an augmenting
path P:
Update flow f by
bottleneck(P,Gf ) along P.
Theorem 3
Suppose all capacities are integers. Then, runtime of O(mC).
Proof.
Theorem 2: termination happens in at most C iterations.
Work per iteration: Overall: O(m)
1 Find an augmenting path: BFS or DFS: O(m + n) .
2 Update flow along path P: O(n).
3 Build new Gf : O(m).
10/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Choosing Good Augmenting Paths
t
u
s
v
100
100
1
100
100
Idea
Choose paths with large
bottlenecks.
Let Gf (∆) be a residual graph
with edges of residual capacity
≥ ∆.
Scaled Version
Initialize f (e) = 0 for all edges.
Initialize ∆ := maxi
(2i) such that 2i ≤ maxe out of s(ce).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P,Gf (∆)) along P.
Set ∆ := ∆/2.
11/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Choosing Good Augmenting Paths
t
u
s
v
100
100
1
100
100
Idea
Choose paths with large
bottlenecks.
Let Gf (∆) be a residual graph
with edges of residual capacity
≥ ∆.
Scaled Version
Initialize f (e) = 0 for all edges.
Initialize ∆ := maxi
(2i) such that 2i ≤ maxe out of s(ce).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P,Gf (∆)) along P.
Set ∆ := ∆/2.
11/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Choosing Good Augmenting Paths
t
u
s
v
100
100
1
100
100
Idea
Choose paths with large
bottlenecks.
Let Gf (∆) be a residual graph
with edges of residual capacity
≥ ∆.
Scaled Version
Initialize f (e) = 0 for all edges.
Initialize ∆ := maxi
(2i) such that 2i ≤ maxe out of s(ce).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P,Gf (∆)) along P.
Set ∆ := ∆/2.
11/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Scaled Version
Scaled Version
Initialize f (e) = 0 for all edges.
Initialize ∆ := maxi
(2i) such that 2i ≤ maxe out of s(ce).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P,Gf (∆)) along P.
Set ∆ := ∆/2.
Termination
As before, inner loop always terminates.
Outer loop advances to 1.
12/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Scaled Version
Scaled Version
Initialize f (e) = 0 for all edges.
Initialize ∆ := maxi
(2i) such that 2i ≤ maxe out of s(ce).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P,Gf (∆)) along P.
Set ∆ := ∆/2.
Advancement
As before, inner loop always improves the flow.
Since last outer iteration has ∆ = 1, this returns the same
max-flow value as the non-scaled version.
12/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Scaled Version
Scaled Version
Initialize f (e) = 0 for all edges.
Initialize ∆ := maxi
(2i) such that 2i ≤ maxe out of s(ce).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P,Gf (∆)) along P.
Set ∆ := ∆/2.
Runtime
Number of scaling phases: TH11.
Number of augmenting phases per scaling phases: .
Cost per augmentation: .
Overall: O(m2 logC).
12/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Scaled Version
Scaled Version
Initialize f (e) = 0 for all edges.
Initialize ∆ := maxi
(2i) such that 2i ≤ maxe out of s(ce).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P,Gf (∆)) along P.
Set ∆ := ∆/2.
Runtime
Number of scaling phases: 1 + dlgCe.
Number of augmenting phases per scaling phases: .
Cost per augmentation: .
Overall: O(m2 logC).
12/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Scaled Version
Scaled Version
Initialize f (e) = 0 for all edges.
Initialize ∆ := maxi
(2i) such that 2i ≤ maxe out of s(ce).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P,Gf (∆)) along P.
Set ∆ := ∆/2.
Runtime
Number of scaling phases: 1 + dlgCe.
Number of augmenting phases per scaling phases: .
Cost per augmentation: .
Overall: O(m2 logC).
12/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Scaled Version
Scaled Version
Initialize f (e) = 0 for all edges.
Initialize ∆ := maxi
(2i) such that 2i ≤ maxe out of s(ce).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P,Gf (∆)) along P.
Set ∆ := ∆/2.
Runtime
Number of scaling phases: 1 + dlgCe.
Number of augmenting phases per scaling phases: O(m).
Cost per augmentation: .
Overall: O(m2 logC).
12/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Scaled Version
Scaled Version
Initialize f (e) = 0 for all edges.
Initialize ∆ := maxi
(2i) such that 2i ≤ maxe out of s(ce).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P,Gf (∆)) along P.
Set ∆ := ∆/2.
Runtime
Number of scaling phases: 1 + dlgCe.
Number of augmenting phases per scaling phases: O(m).
Cost per augmentation: TH13.
Overall: O(m2 logC).
12/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Scaled Version
Scaled Version
Initialize f (e) = 0 for all edges.
Initialize ∆ := maxi
(2i) such that 2i ≤ maxe out of s(ce).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P,Gf (∆)) along P.
Set ∆ := ∆/2.
Runtime
Number of scaling phases: 1 + dlgCe.
Number of augmenting phases per scaling phases: O(m).
Cost per augmentation: O(m).
Overall: O(m2 logC).
12/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Scaled Version
Scaled Version
Initialize f (e) = 0 for all edges.
Initialize ∆ := maxi
(2i) such that 2i ≤ maxe out of s(ce).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P,Gf (∆)) along P.
Set ∆ := ∆/2.
Runtime
Number of scaling phases: 1 + dlgCe.
Number of augmenting phases per scaling phases: O(m).
Cost per augmentation: O(m).
Overall: O(m2 logC).
12/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Scaled Version
Scaled Version
Initialize f (e) = 0 for all edges.
Initialize ∆ := maxi
(2i) such that 2i ≤ maxe out of s(ce).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P,Gf (∆)) along P.
Set ∆ := ∆/2.
Runtime
Number of scaling phases: 1 + dlgCe.
Number of augmenting phases per scaling phases: O(m).
Cost per augmentation: O(m).
Overall: O(m2 logC).
TopHat 14: Is this polynomial?
12/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Analyzing the Scaled Version
Scaled Version
Initialize f (e) = 0 for all edges.
Initialize ∆ := maxi
(2i) such that 2i ≤ maxe out of s(ce).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P,Gf (∆)) along P.
Set ∆ := ∆/2.
Runtime
Number of scaling phases: 1 + dlgCe.
Number of augmenting phases per scaling phases: O(m).
Cost per augmentation: O(m).
Overall: O(m2 logC).
TopHat 14: Is this polynomial? Yes, because dlogCe is the # of
bits needed to encode C. 12/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Strongly Polynomial
Definition
Polynomial in the dimensions of the problem, not in the
size of the numerical data.
m and n for max-flow.
Fewest Edges Augmenting Path
O(m2n)
Edmonds-Karp (BFS) 1970
Dinitz 1970
Other Variations
Dinitz 1970: O
(
min
{
n 23 ,m 12
}
m
)
.
Preflow-Push 1974/1986: O(n3).
Best: Orlin 2013: O(mn)
13/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Strongly Polynomial
Definition
Polynomial in the dimensions of the problem, not in the
size of the numerical data.
m and n for max-flow.
Fewest Edges Augmenting Path
O(m2n)
Edmonds-Karp (BFS) 1970
Dinitz 1970
Other Variations
Dinitz 1970: O
(
min
{
n 23 ,m 12
}
m
)
.
Preflow-Push 1974/1986: O(n3).
Best: Orlin 2013: O(mn)
13/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Strongly Polynomial
Definition
Polynomial in the dimensions of the problem, not in the
size of the numerical data.
m and n for max-flow.
Fewest Edges Augmenting Path
O(m2n)
Edmonds-Karp (BFS) 1970
Dinitz 1970
Other Variations
Dinitz 1970: O
(
min
{
n 23 ,m 12
}
m
)
.
Preflow-Push 1974/1986: O(n3).
Best: Orlin 2013: O(mn)
13/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Minimum Cut
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow and Min-Cut
Recall Cut
A Cut: Partition of V into sets (A,B) with s ∈ A and t ∈ B.
Cut capacity: c(A,B) = ∑e out of A ce.
Lemma 4
Let f be any s− t flow and (A,B) be any s− t cut. Then,
v(f ) = f out(A)− f in(A) = f in(B)− f out(B) .
14/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow and Min-Cut
Recall Cut
A Cut: Partition of V into sets (A,B) with s ∈ A and t ∈ B.
Cut capacity: c(A,B) = ∑e out of A ce.
Lemma 4
Let f be any s− t flow and (A,B) be any s− t cut. Then,
v(f ) = f out(A)− f in(A) = f in(B)− f out(B) .
14/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow and Min-Cut
Lemma 4
Let f be any s− t flow and (A,B) be any s− t cut. Then,
v(f ) = f out(A)− f in(A) = f in(B)− f out(B) .
Proof.
By definition, f out(A) = f in(B) and f in(A) = f out(B).
By definition, v(f ) = f out(s)
= f out(s)− f in(s)
=
∑
v∈A
(f out(v)− f in(v))
Last line follows since∑v∈A\{s} (f out(v)− f in(v)) = 0.∑
v∈A
(f out(v)− f in(v)) = ∑
e out of A
f (e)−
∑
e into A
f (e) = f out(A)−f in(A) .
14/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow and Min-Cut
Lemma 4
Let f be any s− t flow and (A,B) be any s− t cut. Then,
v(f ) = f out(A)− f in(A) = f in(B)− f out(B) .
Proof.
By definition, f out(A) = f in(B) and f in(A) = f out(B).
By definition, v(f ) = f out(s)
= f out(s)− f in(s)
=
∑
v∈A
(f out(v)− f in(v))
Last line follows since∑v∈A\{s} (f out(v)− f in(v)) = 0.∑
v∈A
(f out(v)− f in(v)) = ∑
e out of A
f (e)−
∑
e into A
f (e) = f out(A)−f in(A) .
14/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow and Min-Cut
Lemma 4
Let f be any s− t flow and (A,B) be any s− t cut. Then,
v(f ) = f out(A)− f in(A) = f in(B)− f out(B) .
Proof.
By definition, f out(A) = f in(B) and f in(A) = f out(B).
By definition, v(f ) = f out(s)
= f out(s)− f in(s)
=
∑
v∈A
(f out(v)− f in(v))
Last line follows since∑v∈A\{s} (f out(v)− f in(v)) = 0.∑
v∈A
(f out(v)− f in(v)) = ∑
e out of A
f (e)−
∑
e into A
f (e) = f out(A)−f in(A) .
14/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow and Min-Cut
Lemma 4
Let f be any s− t flow and (A,B) be any s− t cut. Then,
v(f ) = f out(A)− f in(A) = f in(B)− f out(B) .
Lemma 5
Let f be any s− t flow and (A,B) be any s− t cut. Then,
v(f ) ≤ c(A,B).
Proof.
v(f ) = f out(A)− f in(A) ≤ f out(A) =
∑
e out of A
f (e)
≤
∑
e out of A
ce = c(A,B)
14/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow and Min-Cut
Lemma 4
Let f be any s− t flow and (A,B) be any s− t cut. Then,
v(f ) = f out(A)− f in(A) = f in(B)− f out(B) .
Lemma 5
Let f be any s− t flow and (A,B) be any s− t cut. Then,
v(f ) ≤ c(A,B).
Proof.
v(f ) = f out(A)− f in(A) ≤ f out(A) =
∑
e out of A
f (e)
≤
∑
e out of A
ce = c(A,B)
14/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow equals Min-Cut
Theorem 6
If f is a s− t flow such that there is no s− t path in Gf , then there is
an s− t cut (A∗,B∗) in G for which v(f ) = c(A∗,B∗).
15/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow equals Min-Cut
Theorem 6
If f is a s− t flow such that there is no s− t path in Gf , then there is
an s− t cut (A∗,B∗) in G for which v(f ) = c(A∗,B∗).
Proof.
Let A∗ be the set of nodes for which ∃ an s− v path in Gf .
Let B∗ = V \ A∗.
Consider e = (u, v): Claim f (e) = ce.
Consider e = (u′, v′): Claim f (e) = 0.
Therefore, v(f ) = f out(A∗)− f in(A∗)
=
∑
e out A∗
ce − 0
= c(A∗,B∗)
15/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow equals Min-Cut
Theorem 6
If f is a s− t flow such that there is no s− t path in Gf , then there is
an s− t cut (A∗,B∗) in G for which v(f ) = c(A∗,B∗).
Proof.
Let A∗ be the set of nodes for which ∃ an s− v path in Gf .
Let B∗ = V \ A∗.
(A∗,B∗) is an s− t cut:
Partition of V
s ∈ A∗ and t ∈ B∗
Consider e = (u, v): Claim f (e) = ce.
Consider e = (u′, v′): Claim f (e) = 0.
Therefore, v(f ) = f out(A∗)− f in(A∗)
=
∑
e out A∗
ce − 0
= c(A∗,B∗)
15/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow equals Min-Cut
Theorem 6
If f is a s− t flow such that there is no s− t path in Gf , then there is
an s− t cut (A∗,B∗) in G for which v(f ) = c(A∗,B∗).
Proof.
Let A∗ be the set of nodes for which ∃ an s− v path in Gf .
Let B∗ = V \ A∗.
Consider e = (u, v): Claim f (e) = ce.
If not, then s− v path in Gf which contradicts definition of
A∗ and B∗.
Consider e = (u′, v′): Claim f (e) = 0.
Therefore, v(f ) = f out(A∗)− f in(A∗)
=
∑
e out A∗
ce − 0
= c(A∗,B∗)
15/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow equals Min-Cut
Theorem 6
If f is a s− t flow such that there is no s− t path in Gf , then there is
an s− t cut (A∗,B∗) in G for which v(f ) = c(A∗,B∗).
Proof.
Let A∗ be the set of nodes for which ∃ an s− v path in Gf .
Let B∗ = V \ A∗.
Consider e = (u′, v′): Claim f (e) = 0.
If not, then s− u′ path in Gf which contradicts definition of
A∗ and B∗.
Therefore, v(f ) = f out(A∗)− f in(A∗)
=
∑
e out A∗
ce − 0
= c(A∗,B∗)
15/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow equals Min-Cut
Theorem 6
If f is a s− t flow such that there is no s− t path in Gf , then there is
an s− t cut (A∗,B∗) in G for which v(f ) = c(A∗,B∗).
Proof.
Let A∗ be the set of nodes for which ∃ an s− v path in Gf .
Let B∗ = V \ A∗.
Consider e = (u, v): Claim f (e) = ce.
Consider e = (u′, v′): Claim f (e) = 0.
Therefore, v(f ) = f out(A∗)− f in(A∗)
=
∑
e out A∗
ce − 0
= c(A∗,B∗)
15/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow equals Min-Cut
Theorem 6
If f is a s− t flow such that there is no s− t path in Gf , then there is
an s− t cut (A∗,B∗) in G for which v(f ) = c(A∗,B∗).
Corollary 7
Let f be flow from Gf with no s− t path. Then, v(f ) = c(A∗,B∗) for
minimum cut (A∗,B∗).
15/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow equals Min-Cut
Theorem 6
If f is a s− t flow such that there is no s− t path in Gf , then there is
an s− t cut (A∗,B∗) in G for which v(f ) = c(A∗,B∗).
Corollary 7
Let f be flow from Gf with no s− t path. Then, v(f ) = c(A∗,B∗) for
minimum cut (A∗,B∗).
Proof.
By way of contradiction, assume v(f ′) > v(f ). This implies
that v(f ′) > c(A∗,B∗) which contradicts Lemma 5.
By way of contradiction, assume c(A,B) < c(A∗,B∗). This
implies that c(A,B) < v(f ) which contradicts Lemma 5.
15/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow equals Min-Cut
Theorem 6
If f is a s− t flow such that there is no s− t path in Gf , then there is
an s− t cut (A∗,B∗) in G for which v(f ) = c(A∗,B∗).
Corollary 7
Let f be flow from Gf with no s− t path. Then, v(f ) = c(A∗,B∗) for
minimum cut (A∗,B∗).
Proof.
By way of contradiction, assume v(f ′) > v(f ). This implies
that v(f ′) > c(A∗,B∗) which contradicts Lemma 5.
By way of contradiction, assume c(A,B) < c(A∗,B∗). This
implies that c(A,B) < v(f ) which contradicts Lemma 5.
15/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Max-Flow equals Min-Cut
Theorem 6
If f is a s− t flow such that there is no s− t path in Gf , then there is
an s− t cut (A∗,B∗) in G for which v(f ) = c(A∗,B∗).
Corollary 7
Let f be flow from Gf with no s− t path. Then, v(f ) = c(A∗,B∗) for
minimum cut (A∗,B∗).
Corollary 8
Ford-Fulkerson method produces the maximum flow since it terminate
when residual graph has no s− t paths.
15/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Finding the Min-Cut
Theorem 9
Given a maximum flow f , an s− t cut of minimum capacity can be
found in O(m) time.
Proof.
Construct residual graph Gf (O(m) time).
BFS or DFS from s to determine A∗ (O(m + n) time).
B∗ = V \ A∗ (O(n) time).
16/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Finding the Min-Cut
Theorem 9
Given a maximum flow f , an s− t cut of minimum capacity can be
found in O(m) time.
Proof.
Construct residual graph Gf (O(m) time).
BFS or DFS from s to determine A∗ (O(m + n) time).
B∗ = V \ A∗ (O(n) time).
16/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Bipartite Matching
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Bipartite Matching Problem
Definition
Bipartite Graph G = (V = X ∪ Y,E).
All edges go between X and Y.
Matching: M ⊆ E s.t. a node appears in
only one edge.
Goal: Find largest matching
(cardinality).
Reduction to Max-Flow Problem
17/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Bipartite Matching Problem
Definition
Bipartite Graph G = (V = X ∪ Y,E).
All edges go between X and Y.
Matching: M ⊆ E s.t. a node appears in
only one edge.
Goal: Find largest matching
(cardinality).
Reduction to Max-Flow Problem
Goal: Create a flow network based on the the original
problem.
The solution to the flow network must correspond to the
original problem.
The reduction should be efficient.
17/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Bipartite Matching Problem
Definition
Bipartite Graph G = (V = X ∪ Y,E).
All edges go between X and Y.
Matching: M ⊆ E s.t. a node appears in
only one edge.
Goal: Find largest matching
(cardinality).
Reduction to Max-Flow Problem
How can the problem be encoded in a graph?
Source/sink: Are they naturally in the graph encoding, or
do additional nodes and edges have to be added?
For each edge: What is the direction? Is it bi-directional?
What is the capacity?
17/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Bipartite Matching to Flow Network
G G′
Add source connected to all X.
Add sink connected to all Y.
Original edges go from X to Y.
Capacity of all edges is 1.
18/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Bipartite Matching to Flow Network
G G′
Theorem 10
|M∗| in G is equal to the max-flow of G′, and the edges carrying the
flow correspond to the edges in the maximum matching.
18/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Bipartite Matching to Flow Network
Theorem 10
|M∗| in G is equal to the max-flow of G′, and the edges carrying the
flow correspond to the edges in the maximum matching.
Proof.
s can send at most 1 unit of flow to each node in X.
Since f in = f out for internal nodes, Y nodes can have at
most 1 flow from 1 node in X.
18/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Bipartite Matching to Flow Network
Theorem 10
|M∗| in G is equal to the max-flow of G′, and the edges carrying the
flow correspond to the edges in the maximum matching.
Proof.
s can send at most 1 unit of flow to each node in X.
Since f in = f out for internal nodes, Y nodes can have at
most 1 flow from 1 node in X.
18/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Bipartite Matching to Flow Network
G G′
Runtime
Assume n = |X| = |Y|,m = |E|.
Overall: .
Basic FF method bound: O(mC), where C = f out(S) ≤ n.
18/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Bipartite Matching to Flow Network
G G′
Runtime
Assume n = |X| = |Y|,m = |E|.
Overall: TH15.
Basic FF method bound: O(mC), where C = f out(S) ≤ n.
18/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Bipartite Matching to Flow Network
G G′
Runtime
Assume n = |X| = |Y|,m = |E|.
Overall: O(mn).
Basic FF method bound: O(mC), where C = f out(S) ≤ n.
18/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Bipartite Matching to Flow Network
G G′
Runtime
Assume n = |X| = |Y|,m = |E|.
Overall: O(mn).
Basic FF method bound: O(mC), where C = f out(S) ≤ n.
18/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Edge-Disjoint Paths
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Edge-Disjoint Paths
Problem
Given a graph G = (V,E) and two distinguished nodes s and t,
find the number of edge-disjoint paths from s to t.
Flow Network
Directed Graph:
s is the source and t is the sink.
Add capacity of 1 to every edge.
Undirected Graph:
For each undirected edge (u, v), convert to 2 directed edges
(u, v) and (v,u).
Apply directed graph transformation.
19/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Edge-Disjoint Paths
Problem
Given a graph G = (V,E) and two distinguished nodes s and t,
find the number of edge-disjoint paths from s to t.
Flow Network
Directed Graph:
s is the source and t is the sink.
Add capacity of 1 to every edge.
Undirected Graph:
For each undirected edge (u, v), convert to 2 directed edges
(u, v) and (v,u).
Apply directed graph transformation.
19/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Edge-Disjoint Paths
Problem
Given a graph G = (V,E) and two distinguished nodes s and t,
find the number of edge-disjoint paths from s to t.
Flow Network
Directed Graph:
s is the source and t is the sink.
Add capacity of 1 to every edge.
Undirected Graph:
For each undirected edge (u, v), convert to 2 directed edges
(u, v) and (v,u).
Apply directed graph transformation.
19/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Edge-Disjoint Paths
Problem
Given a graph G = (V,E) and two distinguished nodes s and t,
find the number of edge-disjoint paths from s to t.
Flow Network
Directed Graph:
s is the source and t is the sink.
Add capacity of 1 to every edge.
Undirected Graph:
For each undirected edge (u, v), convert to 2 directed edges
(u, v) and (v,u).
Apply directed graph transformation.
19/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Edge-Disjoint Paths
Problem
Given a graph G = (V,E) and two distinguished nodes s and t,
find the number of edge-disjoint paths from s to t.
Flow Network
Directed Graph:
s is the source and t is the sink.
Add capacity of 1 to every edge.
Undirected Graph:
For each undirected edge (u, v), convert to 2 directed edges
(u, v) and (v,u).
Apply directed graph transformation.
19/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Edge-Disjoint Paths Analysis
Observation 3
If there are k edge-disjoint paths in G from s− t, then the max-flow is
k in G′.
Runtime
Basic FF method: O(mC) = O(mn).
Path Decomposition
Let f be a max-flow for this problem. How can we recover
the k edge-disjoint paths?
DFS from s in f along edges e, where f (e) = 1:
1 Find a simple path P from s to t: set flow to 0 along P;
continue DFS from s.
2 Find a path P with a cycle C before reaching t: set flow to 0
along C; continue DFS from start of cycle.
20/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Edge-Disjoint Paths Analysis
Observation 3
If there are k edge-disjoint paths in G from s− t, then the max-flow is
k in G′.
Runtime
Basic FF method: O(mC) = O(mn).
Path Decomposition
Let f be a max-flow for this problem. How can we recover
the k edge-disjoint paths?
DFS from s in f along edges e, where f (e) = 1:
1 Find a simple path P from s to t: set flow to 0 along P;
continue DFS from s.
2 Find a path P with a cycle C before reaching t: set flow to 0
along C; continue DFS from start of cycle.
20/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Edge-Disjoint Paths Analysis
Observation 3
If there are k edge-disjoint paths in G from s− t, then the max-flow is
k in G′.
Runtime
Basic FF method: O(mC) = O(mn).
Path Decomposition
Let f be a max-flow for this problem. How can we recover
the k edge-disjoint paths?
DFS from s in f along edges e, where f (e) = 1:
1 Find a simple path P from s to t: set flow to 0 along P;
continue DFS from s.
2 Find a path P with a cycle C before reaching t: set flow to 0
along C; continue DFS from start of cycle.
20/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Edge-Disjoint Paths Analysis
Observation 3
If there are k edge-disjoint paths in G from s− t, then the max-flow is
k in G′.
Runtime
Basic FF method: O(mC) = O(mn).
Path Decomposition
Let f be a max-flow for this problem. How can we recover
the k edge-disjoint paths?
DFS from s in f along edges e, where f (e) = 1:
1 Find a simple path P from s to t: set flow to 0 along P;
continue DFS from s.
2 Find a path P with a cycle C before reaching t: set flow to 0
along C; continue DFS from start of cycle.
20/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Node Demand and LowerBounds
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Flow Network Extension
Adding Node Demand
Flow Network with Demand
Each node has a demand dv:
if dv < 0: a source that demands f in(v)− f out(v) = dv.
if dv = 0: internal node (f in(v)− f out(v) = 0).
if dv > 0: a sink that demands f in(v)− f out(v) = dv.
S is the set of sources (dv < 0).
T is the set of sinks (dv > 0).
Flow Conditions
i Capacity: For each e ∈ E, 0 ≤ f (e) ≤ ce.
ii Conservation: For each v ∈ V, f in(v)− f out(v) = dv.
Goal
Feasibility: Does there exist a flow that satisfies the conditions?
21/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Flow Network Extension
Adding Node Demand
Flow Network with Demand
Each node has a demand dv:
if dv < 0: a source that demands f in(v)− f out(v) = dv.
if dv = 0: internal node (f in(v)− f out(v) = 0).
if dv > 0: a sink that demands f in(v)− f out(v) = dv.
S is the set of sources (dv < 0).
T is the set of sinks (dv > 0).
Flow Conditions
i Capacity: For each e ∈ E, 0 ≤ f (e) ≤ ce.
ii Conservation: For each v ∈ V, f in(v)− f out(v) = dv.
Goal
Feasibility: Does there exist a flow that satisfies the conditions?
21/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Flow Network Extension
Adding Node Demand
Flow Network with Demand
Each node has a demand dv:
if dv < 0: a source that demands f in(v)− f out(v) = dv.
if dv = 0: internal node (f in(v)− f out(v) = 0).
if dv > 0: a sink that demands f in(v)− f out(v) = dv.
S is the set of sources (dv < 0).
T is the set of sinks (dv > 0).
Flow Conditions
i Capacity: For each e ∈ E, 0 ≤ f (e) ≤ ce.
ii Conservation: For each v ∈ V, f in(v)− f out(v) = dv.
Goal
Feasibility: Does there exist a flow that satisfies the conditions?
21/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Feasibility
Goal
Feasibility: Does there exist a flow that satisfies the conditions?
Lemma 10
If there is a feasible flow, then∑v∈V dv = 0.
22/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Feasibility
Goal
Feasibility: Does there exist a flow that satisfies the conditions?
Lemma 10
If there is a feasible flow, then∑v∈V dv = 0.
Proof.
Suppose that f is a feasible flow, then, by definition, for all
v, dv = f in(v)− f out(v).
For every edge e = (u, v), f oute (u) = f ine (v). Hence,
f ine (v)− f oute (u) = 0.∑
v∈V dv = 0.
22/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Feasibility
Goal
Feasibility: Does there exist a flow that satisfies the conditions?
Lemma 10
If there is a feasible flow, then∑v∈V dv = 0.
Proof.
Suppose that f is a feasible flow, then, by definition, for all
v, dv = f in(v)− f out(v).
For every edge e = (u, v), f oute (u) = f ine (v). Hence,
f ine (v)− f oute (u) = 0.
∑
v∈V dv = 0.
22/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Feasibility
Goal
Feasibility: Does there exist a flow that satisfies the conditions?
Lemma 10
If there is a feasible flow, then∑v∈V dv = 0.
Proof.
Suppose that f is a feasible flow, then, by definition, for all
v, dv = f in(v)− f out(v).
For every edge e = (u, v), f oute (u) = f ine (v). Hence,
f ine (v)− f oute (u) = 0.∑
v∈V dv = 0.
22/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Feasibility
Goal
Feasibility: Does there exist a flow that satisfies the conditions?
Lemma 10
If there is a feasible flow, then∑v∈V dv = 0.
Corollary 11
If there is a feasible flow, then
D =
∑
v:dv>0∈V
dv =
∑
v:dv<0∈V
−dv
Not iff
Feasibility =⇒ ∑v∈V dv = 0, but∑v∈V dv = 0 6=⇒ feasibility.
22/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Feasibility
Goal
Feasibility: Does there exist a flow that satisfies the conditions?
Lemma 10
If there is a feasible flow, then∑v∈V dv = 0.
Corollary 11
If there is a feasible flow, then
D =
∑
v:dv>0∈V
dv =
∑
v:dv<0∈V
−dv
Not iff
Feasibility =⇒ ∑v∈V dv = 0, but∑v∈V dv = 0 6=⇒ feasibility.
22/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Reduction to Max-Flow
Reduction from G (demands) to G′ (no demands)
Super source s∗: Edges from s∗ to all v ∈ Swith dV < 0
with capacity −dv.
Super sink t∗: Edges from all v ∈ T with dV > 0 with
capacity dv to t∗.
Maximum flow of D = ∑v:dv>0∈V dv = ∑v:dv<0∈V −dv in G′
shows feasibility.
23/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Reduction to Max-Flow
Reduction from G (demands) to G′ (no demands)
Super source s∗: Edges from s∗ to all v ∈ Swith dV < 0
with capacity −dv.
Super sink t∗: Edges from all v ∈ T with dV > 0 with
capacity dv to t∗.
Maximum flow of D = ∑v:dv>0∈V dv = ∑v:dv<0∈V −dv in G′
shows feasibility.
23/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Reduction to Max-Flow
Reduction from G (demands) to G′ (no demands)
Super source s∗: Edges from s∗ to all v ∈ Swith dV < 0
with capacity −dv.
Super sink t∗: Edges from all v ∈ T with dV > 0 with
capacity dv to t∗.
Maximum flow of D = ∑v:dv>0∈V dv = ∑v:dv<0∈V −dv in G′
shows feasibility.
23/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Another Flow Network Extension
Adding Flow Lower Bound
Adding Lower Bound
For each edge e, define a lower bound `e, where 0 ≤ `e ≤ ce.
Flow Conditions
i Capacity: For each e ∈ E, `e ≤ f (e) ≤ ce.
ii Conservation: For each v ∈ V, f in(v)− f out(v) = dv.
Goal
Feasibility: Does there exist a flow that satisfies the conditions?
24/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Another Flow Network Extension
Adding Flow Lower Bound
Adding Lower Bound
For each edge e, define a lower bound `e, where 0 ≤ `e ≤ ce.
Flow Conditions
i Capacity: For each e ∈ E, `e ≤ f (e) ≤ ce.
ii Conservation: For each v ∈ V, f in(v)− f out(v) = dv.
Goal
Feasibility: Does there exist a flow that satisfies the conditions?
24/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Another Flow Network Extension
Adding Flow Lower Bound
Adding Lower Bound
For each edge e, define a lower bound `e, where 0 ≤ `e ≤ ce.
Flow Conditions
i Capacity: For each e ∈ E, `e ≤ f (e) ≤ ce.
ii Conservation: For each v ∈ V, f in(v)− f out(v) = dv.
Goal
Feasibility: Does there exist a flow that satisfies the conditions?
24/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Reduction to Only Demand
Step 1: Reduction from G (demand + LB) to G′ (demand)
Consider an f0 that sets all edge flows to `e:
Lv = f in0 (v)− f out0 (v) .
if Lv = dv: Condition is satisfied.
if Lv 6= dv: Imbalance.
For G′:
Each edge e, c′e = ce − `e and `e = 0.
Each node v, d′v = dv − Lv.
25/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Reduction to Only Demand
Step 1: Reduction from G (demand + LB) to G′ (demand)
Consider an f0 that sets all edge flows to `e:
Lv = f in0 (v)− f out0 (v) .
if Lv = dv: Condition is satisfied.
if Lv 6= dv: Imbalance.
For G′:
Each edge e, c′e = ce − `e and `e = 0.
Each node v, d′v = dv − Lv. 25/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Reduction to Only Demand
Step 2: Reduction from G′ (demand) to G′′ (no demand)
Super source s∗: Edges from s∗ to all v ∈ Swith dV < 0
with capacity −dv.
Super sink t∗: Edges from all v ∈ T with dV > 0 with
capacity dv to t∗.
Maximum flow of D = ∑v:dv>0∈V dv = ∑v:dv<0∈V −dv in G′
shows feasibility.
25/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Survey Design
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Survey Design
Problem
Study of consumer preferences.
A company, with k products, has a
database of n customer purchase
histories.
Goal: Define a product specific
survey.
Survey Rules
Each customer receives a survey based on their purchases.
Customer i will be asked about at least ci and at most c′i
products.
To be useful, each product must appear in at least pi and at
most p′i surveys.
26/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Survey Design
Problem
Study of consumer preferences.
A company, with k products, has a
database of n customer purchase
histories.
Goal: Define a product specific
survey.
Survey Rules
Each customer receives a survey based on their purchases.
Customer i will be asked about at least ci and at most c′i
products.
To be useful, each product must appear in at least pi and at
most p′i surveys.
26/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Survey Design
Problem
Study of consumer preferences.
A company, with k products, has a
database of n customer purchase
histories.
Goal: Define a product specific
survey.
Survey Rules
Each customer receives a survey based on their purchases.
Customer i will be asked about at least ci and at most c′i
products.
To be useful, each product must appear in at least pi and at
most p′i surveys.
26/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Survey Design
Problem
Study of consumer preferences.
A company, with k products, has a
database of n customer purchase
histories.
Goal: Define a product specific
survey.
Survey Rules
Each customer receives a survey based on their purchases.
Customer i will be asked about at least ci and at most c′i
products.
To be useful, each product must appear in at least pi and at
most p′i surveys.
26/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Survey Design
Problem
Study of consumer preferences.
A company, with k products, has a
database of n customer purchase
histories.
Goal: Define a product specific
survey.
TopHat 16: What
type of graph to
use?
Survey Rules
Each customer receives a survey based on their purchases.
Customer i will be asked about at least ci and at most c′i
products.
To be useful, each product must appear in at least pi and at
most p′i surveys.
26/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
27/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
27/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
27/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Reduction
Bipartite Graph: Customers to products with min of 0 and
max of 1.
Add swith edges to customer iwith min of ci and max of c′i.
Add twith edges from product j with min pj and max of p′j.
Edge (t, s) with min∑i ci and max∑i c′i.
All nodes have a demand of 0.
27/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Solution
Feasibility means it is possible to meet the constraints.
Edge (i, j) carries flow if customer i asked about product j.
Flow (t, s) overall # of questions.
Flow (s, i) # of products evaluated by customer i.
Flow (j, t) # of customers asked about product j.
27/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Airline Scheduling
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Airline Scheduling
Flights: (2 airplanes)
1 Boston (6 am) – Washington DC (7 am)
2 Philadelphia (7 am) – Pittsburgh (8 am)
3 Washington DC (8 am) – Los Angeles (11 am)
4 Philadelphia (11 am) – San Francisco (2 pm)
5 San Francisco (2:15 pm) – Seattle (3:15 pm)
6 Las Vegas (5 pm) – Seattle (6 pm)
Simple Version
Scheduling a fleet of k airplanes.
m flight segments, for segment i:
Origin and departure time.
Destination and arrival time.
28/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Airline Scheduling
Flights: (2 airplanes)
1 Boston (6 am) – Washington DC (7 am)
2 Philadelphia (7 am) – Pittsburgh (8 am)
3 Washington DC (8 am) – Los Angeles (11 am)
4 Philadelphia (11 am) – San Francisco (2 pm)
5 San Francisco (2:15 pm) – Seattle (3:15 pm)
6 Las Vegas (5 pm) – Seattle (6 pm)
Rules
The same plane can be used for flight i and j if:
i destination is the same as j origin and there is enough
time for maintenance between i arrival and j departure;
Or, there is enough time for maintenance and to fly from i
destination to j origin.
How might you represent this as a graph?
28/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Airline Scheduling
Flights: (2 airplanes)
1 Boston (6 am) – Washington DC (7 am)
2 Philadelphia (7 am) – Pittsburgh (8 am)
3 Washington DC (8 am) – Los Angeles (11 am)
4 Philadelphia (11 am) – San Francisco (2 pm)
5 San Francisco (2:15 pm) – Seattle (3:15 pm)
6 Las Vegas (5 pm) – Seattle (6 pm)
Rules
The same plane can be used for flight i and j if:
i destination is the same as j origin and there is enough
time for maintenance between i arrival and j departure;
Or, there is enough time for maintenance and to fly from i
destination to j origin.
How might you represent this as a graph?
28/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Airline Scheduling
Flights: (2 airplanes)
1 Boston (6 am) – Washington DC (7 am)
2 Philadelphia (7 am) – Pittsburgh (8 am)
3 Washington DC (8 am) – Los Angeles (11 am)
4 Philadelphia (11 am) – San Francisco (2 pm)
5 San Francisco (2:15 pm) – Seattle (3:15 pm)
6 Las Vegas (5 pm) – Seattle (6 pm)
Rules
The same plane can be used for flight i and j if:
i destination is the same as j origin and there is enough
time for maintenance between i arrival and j departure;
Or, there is enough time for maintenance and to fly from i
destination to j origin.
How might you represent this as a graph?
28/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
k = 2 planes
Exercise: Reduce to a flow network
Hint: Use lower bounds and demand.
29/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
k = 2 planes
Exercise: Reduce to a flow network
Hint: Use lower bounds and demand.
TH17: Are s-t new nodes?
TH18: What is the max capacity of the edges from G?
29/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
k = 2 planes
Exercise: Reduce to a flow network
Hint: Use lower bounds and demand.
TH19: In the example, how many edges out from s?
TH20: In the example, how many edges in to t?
29/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
k = 2 planes
Reduction
Units of flow correspond to airplanes.
Each edge of a flight has capacity (1, 1).
Each edge between flights has capacity of (0, 1).
Add node s with edges to all origins with capacity of (0, 1).
Add node twith edges from all destinations with cap (0, 1).
Edge (s, t) with a min of 0 and a max of k.
Demand: ds = −k, dt = k, dv = 0∀v ∈ V \ {s, t}.
29/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Project Selection
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Project Selection
Use Min-Cut to solve this
problem.
Problem
Set of projects: P.
Each i ∈ P: profit pi (which can be negative).
Directed graph G encoding precedence constraints.
Feasible set of projects A: profit(A) = ∑i∈A pi.
Goal: Find A∗ that maximizes profit.
30/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Project Selection
Use Min-Cut to solve this
problem.
Problem
Set of projects: P.
Each i ∈ P: profit pi (which can be negative).
Directed graph G encoding precedence constraints.
Feasible set of projects A: profit(A) = ∑i∈A pi.
Goal: Find A∗ that maximizes profit.
30/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Reduction
Use Min-Cut
Add s with edge to every
project i with pi > 0 and
capacity pi.
Add t with edge from every
project i with pi < 0 and
capacity −pi.
C = ∑i∈P:pi>0 pi
For edges of G, capacity is∞
(or C + 1).
31/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Reduction
Use Min-Cut
Add s with edge to every
project i with pi > 0 and
capacity pi.
Add t with edge from every
project i with pi < 0 and
capacity −pi.
C = ∑i∈P:pi>0 pi
For edges of G, capacity is∞
(or C + 1).
31/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Reduction
Use Min-Cut
Add s with edge to every
project i with pi > 0 and
capacity pi.
Add t with edge from every
project i with pi < 0 and
capacity −pi.
C = ∑i∈P:pi>0 pi
For edges of G, capacity is∞
(or C + 1).
31/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Reduction
Use Min-Cut
Add s with edge to every
project i with pi > 0 and
capacity pi.
Add t with edge from every
project i with pi < 0 and
capacity −pi.
C = ∑i∈P:pi>0 pi
For edges of G, capacity is∞
(or C + 1).
31/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Reduction
Use Min-Cut
Add s with edge to every
project i with pi > 0 and
capacity pi.
Add t with edge from every
project i with pi < 0 and
capacity −pi.
C = ∑i∈P:pi>0 pi
TH21: What is the capacity of
the cut ({s},P ∪ {t})?
For edges of G, capacity is∞
(or C + 1).
31/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Reduction
Use Min-Cut
Add s with edge to every
project i with pi > 0 and
capacity pi.
Add t with edge from every
project i with pi < 0 and
capacity −pi.
Max-flow is
≤ C = ∑i∈P:pi>0 pi which is
the capacity ({s},P ∪ {t})
For edges of G, capacity is∞
(or C + 1).
31/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Reduction
Use Min-Cut
Add s with edge to every
project i with pi > 0 and
capacity pi.
Add t with edge from every
project i with pi < 0 and
capacity −pi.
Max-flow is
≤ C = ∑i∈P:pi>0 pi .
For edges of G, capacity is∞
(or C + 1).
31/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Analysis
Observation 4
If c(A′,B′) ≤ C, then A = A′ \ {s}
satisfies precedence as edges of G have
capacity > C.
Lemma 12
Let (A′,B′) be a cut satisfies
precedence; then
c(A′,B′) = C −∑i∈A pi.
Proof.
Consider the different edges:
(i, t): −pi for i ∈ A. (s, i): pi for i /∈ A.
c(A′,B′) = ∑i∈A:pi<0−pi + C −∑i∈A:pi>0 pi = C −∑i∈A pi
32/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Analysis
Observation 4
If c(A′,B′) ≤ C, then A = A′ \ {s}
satisfies precedence as edges of G have
capacity > C.
Lemma 12
Let (A′,B′) be a cut satisfies
precedence; then
c(A′,B′) = C −∑i∈A pi.
Proof.
Consider the different edges:
(i, t): −pi for i ∈ A. (s, i): pi for i /∈ A.
c(A′,B′) = ∑i∈A:pi<0−pi + C −∑i∈A:pi>0 pi = C −∑i∈A pi
32/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Analysis
Observation 4
If c(A′,B′) ≤ C, then A = A′ \ {s}
satisfies precedence as edges of G have
capacity > C.
Lemma 12
Let (A′,B′) be a cut satisfies
precedence; then
c(A′,B′) = C −∑i∈A pi.
Proof.
Consider the different edges:
(i, t): −pi for i ∈ A. (s, i): pi for i /∈ A.
c(A′,B′) = ∑i∈A:pi<0−pi + C −∑i∈A:pi>0 pi = C −∑i∈A pi
32/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Analysis
Theorem 12
If (A′,B′) is a min-cut in G′, then
A = A′ \ {s} is an optimal solution.
Proof.
Obs: c(A′,B′) = C −∑i∈A pi
means feasible.
c(A′,B′) = C − profit(A)
⇐⇒ profit(A) = C − c(A′,B′)
Given that c(A′,B′) is a
minimum, profit is
maximized as C is a constant.
32/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Analysis
Theorem 12
If (A′,B′) is a min-cut in G′, then
A = A′ \ {s} is an optimal solution.
Proof.
Obs: c(A′,B′) = C −∑i∈A pi
means feasible.
c(A′,B′) = C − profit(A)
⇐⇒ profit(A) = C − c(A′,B′)
Given that c(A′,B′) is a
minimum, profit is
maximized as C is a constant.
32/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Baseball Elimination
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Baseball Elimination
Wins Games Left
New York 92 NYY vs TOR
Toronto 91 TOR vs BAL
Baltimore 91 BAL vs BOS
Boston 90 BOS vs TOR
NYY vs BAL
33/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Baseball Elimination
Wins Games Left
New York 92 NYY vs TOR
Toronto 91 TOR vs BAL
Baltimore 91 BAL vs BOS
Boston 90 BOS vs TOR
NYY vs BAL
TH22: Is Boston Eliminated?
33/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Baseball Elimination
Wins Games Left
New York 92 NYY vs TOR
Toronto 91 TOR vs BAL
Baltimore 91 BAL vs BOS
Boston 90 BOS vs TOR
NYY vs BAL
TH22: Is Boston Eliminated? Yes.
33/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Baseball Elimination
Wins Games Left
New York 92 NYY vs TOR
Toronto 91 TOR vs BAL
Baltimore 91 BAL vs BOS
Boston 90 BOS vs TOR
NYY vs BAL
Why is Boston eliminated?
Case analysis:
Boston must win its 2 remaining games.
New York must lose its 2 remaining games.
This leaves TOR vs BAL: So one of Toronto or Baltimore
will end with 93 wins.
33/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Baseball Elimination
Wins Games Left
New York 92 NYY vs TOR
Toronto 91 TOR vs BAL
Baltimore 91 BAL vs BOS
Boston 90 BOS vs TOR
NYY vs BAL
Why is Boston eliminated?
Case analysis:
Boston must win its 2 remaining games.
New York must lose its 2 remaining games.
This leaves TOR vs BAL: So one of Toronto or Baltimore
will end with 93 wins.
33/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Baseball Elimination
Wins Games Left
New York 92 NYY vs TOR
Toronto 91 TOR vs BAL
Baltimore 91 BAL vs BOS
Boston 90 BOS vs TOR
NYY vs BAL
Why is Boston eliminated?
Case analysis:
Boston must win its 2 remaining games.
New York must lose its 2 remaining games.
This leaves TOR vs BAL: So one of Toronto or Baltimore
will end with 93 wins.
33/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Baseball Elimination
Wins Games Left
New York 92 NYY vs TOR
Toronto 91 TOR vs BAL
Baltimore 91 BAL vs BOS
Boston 90 BOS vs TOR
NYY vs BAL
Why is Boston eliminated?
Analytical approach:
Boston can finish with ≤ 92 wins.
Currently, other 3 teams have 274 combined wins with 3
remaining games between them:
Overall, at the end, there will be 277 combined wins
between the other 3 teams.
Average of 92 1/3 wins which implies that one team will
have at least 92 1/3 =⇒ 93 wins.
33/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Baseball Elimination
Wins Games Left
New York 92 NYY vs TOR
Toronto 91 TOR vs BAL
Baltimore 91 BAL vs BOS
Boston 90 BOS vs TOR
NYY vs BAL
Why is Boston eliminated?
Analytical approach:
Boston can finish with ≤ 92 wins.
Currently, other 3 teams have 274 combined wins with 3
remaining games between them:
Overall, at the end, there will be 277 combined wins
between the other 3 teams.
Average of 92 1/3 wins which implies that one team will
have at least 92 1/3 =⇒ 93 wins.
33/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Baseball Elimination
Wins Games Left
New York 92 NYY vs TOR
Toronto 91 TOR vs BAL
Baltimore 91 BAL vs BOS
Boston 90 BOS vs TOR
NYY vs BAL
Why is Boston eliminated?
Analytical approach:
Boston can finish with ≤ 92 wins.
Currently, other 3 teams have 274 combined wins with 3
remaining games between them:
Overall, at the end, there will be 277 combined wins
between the other 3 teams.
Average of 92 1/3 wins which implies that one team will
have at least 92 1/3 =⇒ 93 wins.
33/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Baseball Elimination
Wins Games Left
New York 92 NYY vs TOR
Toronto 91 TOR vs BAL
Baltimore 91 BAL vs BOS
Boston 90 BOS vs TOR
NYY vs BAL
Why is Boston eliminated?
Analytical approach:
Boston can finish with ≤ 92 wins.
Currently, other 3 teams have 274 combined wins with 3
remaining games between them:
Overall, at the end, there will be 277 combined wins
between the other 3 teams.
Average of 92 1/3 wins which implies that one team will
have at least 92 1/3 =⇒ 93 wins.
33/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Baseball Elimination
Problem
A set S of teams.
For each team x ∈ S: wx is the # of wins.
For each pair x, y ∈ S: gxy is # of games left btw x and y.
Goal: Decide if team z has been eliminated.
34/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Let m be the max # of
wins for z,
S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Reduction
Nodes:
Source s, sink t.
vx for each x ∈ S′.
uxy for each pair x, y ∈ S′.
35/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Let m be the max # of
wins for z,
S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Reduction
Edges:
For each vx: (vx, t) with capacity m− wx.
For each uxy:
(s, uxy) with capacity gxy.
(uxy, vx) and (uxy, vy) with capacity∞ (or gxy).
35/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Let m be the max # of
wins for z,
S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Solution
v(f ) = g∗: z is not eliminated.
v(f ) < g∗: z is eliminated.
35/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Let m be the max # of
wins for z,
S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Solution
v(f ) = g∗: z is not eliminated.
v(f ) = g∗ = f in(t) ≤
∑
x∈S′
(m− wx) = m|S′| −
∑
x∈S′
wx
⇐⇒
∑
x,y∈S′
gxy ≤ m|S′| −
∑
x∈S′
wx
v(f ) < g∗: z is eliminated.
35/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Let m be the max # of
wins for z,
S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Solution
v(f ) = g∗: z is not eliminated.
v(f ) = g∗ = f in(t) ≤
∑
x∈S′
(m− wx) = m|S′| −
∑
x∈S′
wx
⇐⇒ m|S′| ≥
∑
x,y∈S′
gxy +
∑
x∈S′
wx
v(f ) < g∗: z is eliminated.
35/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Let m be the max # of
wins for z,
S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Solution
v(f ) = g∗: z is not eliminated.
v(f ) = g∗ = f in(t) ≤
∑
x∈S′
(m− wx) = m|S′| −
∑
x∈S′
wx
⇐⇒ m ≥ (
∑
x,y∈S′
gxy +
∑
x∈S′
wx)/|S′|
v(f ) < g∗: z is eliminated.
35/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Algorithm Design
Let m be the max # of
wins for z,
S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Solution
v(f ) = g∗: z is not eliminated.
v(f ) < g∗: z is eliminated.
35/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Solution Characterization
Let m be the max # of
wins for z,
S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Theorem 13
Suppose z has been eliminated. Then, there is a set of items T ⊆ S′
such that: m|T| <∑x,y∈T gxy +∑x∈T wx
36/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Solution Characterization
Let m be the max # of wins for
z, S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Theorem 13
Suppose z has been eliminated. Then, there is a set of items T ⊆ S′
such that: m|T| <∑x,y∈T gxy +∑x∈T wx
Proof.
Let (A,B) be a min-cut with
c(A,B) = g′ ≤ min{∑x,y∈S′ gxy,∑x∈S′ m− wx}.
Consider a uxy ∈ A, x ∈ T, and y /∈ T (WLOG).
Contradiction: c(uxy,y) =∞.
36/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Solution Characterization
Let m be the max # of wins for
z, S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Theorem 13
Suppose z has been eliminated. Then, there is a set of items T ⊆ S′
such that: m|T| <∑x,y∈T gxy +∑x∈T wx
Proof.
Let (A,B) be a min-cut with
c(A,B) = g′ ≤ min{∑x,y∈S′ gxy,∑x∈S′ m− wx}.
Consider a uxy ∈ A, x ∈ T, and y /∈ T (WLOG).
Contradiction: c(uxy,y) =∞.
36/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Solution Characterization
Let m be the max # of wins for
z, S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Theorem 13
Suppose z has been eliminated. Then, there is a set of items T ⊆ S′
such that: m|T| <∑x,y∈T gxy +∑x∈T wx
Proof.
Let (A,B) be a min-cut with
c(A,B) = g′ ≤ min{∑x,y∈S′ gxy,∑x∈S′ m− wx}.
Consider a uxy /∈ A, and x, y ∈ T.
Contradiction: c(A ∪ {uxy},B \ {uxy}) = c(A,B)− gxy.
36/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Solution Characterization
Let m be the max # of wins for
z, S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Theorem 13
Suppose z has been eliminated. Then, there is a set of items T ⊆ S′
such that: m|T| <∑x,y∈T gxy +∑x∈T wx
Proof.
Let (A,B) be a min-cut with
c(A,B) = g′ ≤ min{∑x,y∈S′ gxy,∑x∈S′ m− wx}.
c(A,B) = g′ = m|T| −∑x∈T wx +∑x,y/∈T gxy
36/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Solution Characterization
Let m be the max # of wins for
z, S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Theorem 13
Suppose z has been eliminated. Then, there is a set of items T ⊆ S′
such that: m|T| <∑x,y∈T gxy +∑x∈T wx
Proof.
Let (A,B) be a min-cut with
c(A,B) = g′ ≤ min{∑x,y∈S′ gxy,∑x∈S′ m− wx}.
c(A,B) = g′ = m|T| −∑x∈T wx + g∗ −∑x,y∈T gxy
36/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Solution Characterization
Let m be the max # of wins for
z, S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Theorem 13
Suppose z has been eliminated. Then, there is a set of items T ⊆ S′
such that: m|T| <∑x,y∈T gxy +∑x∈T wx
Proof.
Let (A,B) be a min-cut with
c(A,B) = g′ ≤ min{∑x,y∈S′ gxy,∑x∈S′ m− wx}.
c(A,B) = g′ = m|T| −∑x∈T wx + g∗ −∑x,y∈T gxy
⇐⇒ 0 > m|T| −∑x∈T wx −∑x,y∈T gxy as g′ < g∗
36/36
Network Flow Min-Cut Bipartite Edge-Disjoint Extensions Surveys Flights Projects Baseball
Solution Characterization
Let m be the max # of wins for
z, S′ = S \ {z}, and
g∗ = ∑x,y∈S′ gxy.
Theorem 13
Suppose z has been eliminated. Then, there is a set of items T ⊆ S′
such that: m|T| <∑x,y∈T gxy +∑x∈T wx
Proof.
Let (A,B) be a min-cut with
c(A,B) = g′ ≤ min{∑x,y∈S′ gxy,∑x∈S′ m− wx}.
c(A,B) = g′ = m|T| −∑x∈T wx + g∗ −∑x,y∈T gxy
⇐⇒ m|T| <∑x∈T wx +∑x,y∈T gxy
36/36
Appendix References
Appendix
Appendix References
References
Appendix References
Image Sources I
https://upload.wikimedia.org/wikipedia/en/
2/25/Delbert_Ray_Fulkerson.png
https://angelberh7.wordpress.com/2014/10/
08/biografia-de-lester-randolph-ford-jr/
https://getthematic.com/insights/
customer-survey-design/
https:
//hexaware.com/industries/travel/airlines/
37/36
Appendix References
Image Sources II
http://bluejayhunter.com/2010/01/
which-team-was-better-92-or-93-blue.html
https://brand.wisc.edu/web/logos/
38/36

欢迎咨询51作业君