CS代考程序代写 data mining ER algorithm The University of Sydney

The University of Sydney
Page 1
From Jeff Erickson’s http://algorithms.wtf

Lecture 5 –
Dynamic Programming II (continued)
The University of Sydney
Page 2

6.8 Shortest Paths
The University of Sydney Page 3

Shortest Paths
– Shortest path problem. Given a directed graph G = (V, E), with edge weights cvw, find shortest path from node s to node t.
allow negative weights
2 10 3
9
s
18
30
5
-8
20
7
6
6
15
-16 6
4 19
6 16
t
11
44
The University of Sydney
Page 4

Shortest Paths: Failed Attempts
– Dijkstra. Can fail if negative edge costs.
u
3
sv
-6 t
– Re-weighting. Adding a constant to every edge weight can fail. 55
The University of Sydney
Page 5
2
1
22
s6 6t
3
-3
3
Paths with more edges are penalized more
0

Shortest Paths: Negative Cost Cycles
– Negative cost cycle.
-6
-4 7
– Observation. If some path from s to t contains a negative cost cycle, there does not exist a shortest s-t path; otherwise, there exists one that is simple and thus has at most n – 1 edges.
st
W c(W) < 0 The University of Sydney Page 6 Shortest Paths: Dynamic Programming Problem: Find shortest path from s to t Step 1: Define subproblems OPT(i, v) = length of shortest v-t path P using at most i edges. The University of Sydney Page 7 s vt ≤ i edges Shortest Paths: Dynamic Programming Step 2: Find recurrences v t The University of Sydney Page 8 Case 1: P uses at most i-1 edges. • OPT(i, v) = OPT(i-1, v) ≤ i-1 edges Shortest Paths: Dynamic Programming Step 2: Find recurrences Case 1: P uses at most i-1 edges. • OPT(i, v) = OPT(i-1, v) Case 2: P uses exactly i edges. t • if (v, w) is first edge, then OPT uses (v, w), and then selects best w-t path using at most i-1 edges w t v ≤ i-1 edges v ≤ i-1 edges OPT(i,v) = min{OPT(i-1,v), min [OPT(i-1,w)+cvw] } (v,w)ÎE The University of Sydney Page 9 Shortest Paths: Dynamic Programming Step 3: Solve the base cases OPT(0,t) = 0 and OPT(0,v≠t) = ∞ The University of Sydney Page 10 Shortest Paths: Dynamic Programming Step 1: OPT(i, v) = length of shortest v-t path P using at most i edges. Step 2: Case 1: P uses at most i-1 edges. • OPT(i, v) = OPT(i-1, v) Case 2: P uses exactly i edges. • if (v, w) is first edge, then OPT uses (v, w), and then selects best w-t path using at most i-1 edges Step 3: OPT(0,t) = 0 and OPT(0,v≠t) = ∞ 0 if i=0 and v=t OPT(i,v) = ∞ if i=0 and v≠t min{OPT(i-1,v), min [OPT(i-1,w)+cvw] } otherwise The University of Sydney (v,w)ÎE Page 11 Shortest Paths: Implementation Shortest-Path(G, t) { foreach node v Î V M[0, v] ¬ ¥ M[0, t] ¬ 0 for i = 1 to n-1 foreach node v Î V O(m) O(n) iterations } M[i, v] ¬ M[i-1, v] foreach edge (v, w) Î E M[i,v] ¬ min{M[i,v],M[i-1,w]+cvw} iterations – Analysis. Q(mn) time, Q(n2) working space. Space used by algorithm in addition to input – Finding the shortest paths. Maintain a "successor" for each table entry. Successor(i,v) = next vertex on shortest v-t path with at most i edges. The University of Sydney Page 12 Shortest Paths: Efficient Implementation Shortest-Path(G, t) { foreach node v Î V M[0, v] ¬ ¥ M[0, t] ¬ 0 for i = 1 to n-1 foreach node v Î V } M[i, v] ¬ M[i-1, v] foreach edge (v, w) Î E M[i,v] ¬ min{M[i,v],M[i-1,w]+cvw} only need – Analysis. Q(mn) time, Q(n) working space. M[i-1, *] values – Finding the shortest paths. Maintain a "successor" for vertex. In the i-th iteration, Successor(v) = next vertex on shortest v-t path with at most i edges. The University of Sydney Page 13 In iteration i, Bellman-Ford: Efficient Implementation Push-Based-Shortest-Path(G, s, t) { foreach node v Î V { M[v] ¬ ¥ successor[v] ¬ Æ } M[t] = 0 for i = 1 to n-1 { foreach node w Î V { if (M[w] has been updated in previous iteration) { foreach node v such that (v, w) Î E { if (M[v] > M[w] + cvw) {
M[v] ¬ M[w] + cvw
successor[v] ¬ w }
} }
If no M[w] value changed in iteration i, stop.
}
}
Analysis: Q(mn) time, Q(n) working space. The University of Sydney Page 14

Shortest Paths: Practical Improvements
– Practical improvements
– Maintain only one array M[v] = shortest v-t path that we have
found so far.
– No need to check edges of the form (v, w) unless M[w] changed in previous iteration.
– Theorem: Throughout the algorithm, M[v] is length of some v-t path, and after i rounds of updates, the value M[v] is no larger than the length of shortest v-t path using £ i edges.
– Overall impact
– Working space: O(n).
– Total space (including input): O(m+n)
– Running time: O(mn) worst case, but substantially faster in practice.
The University of Sydney
Page 15
15

Dynamic Programming Summary I
3 steps:
1. Definesubproblems
2. Findrecurrences
3. Solvethebasecases
4. Transformrecurrenceintoanefficientalgorithm [usually bottom-up]
The University of Sydney
Page 16
16

Dynamic Programming Summary II
– 1D dynamic programming
– Weighted interval scheduling
– Segmented Least Squares
– Maximum-sum contiguous subarray – Longest increasing subsequence
– 2D dynamic programming – Knapsack
– Shortest path
– Longest common subsequence
– Dynamic programming over intervals – RNA Secondary Structure
The University of Sydney
Page 17

General techniques in this course
– Greedy algorithms [Lecture 2]
– Divide & Conquer algorithms [Lecture 3]
– Dynamic programming algorithms [Lectures 4 and 5] – Network flow algorithms [today and Lecture 7-8]
– Theory [today]
– Applications [Lectures 7-8]
– NP and NP-completeness – Coping with hardness
The University of Sydney
Page 18

Soviet Rail Network, 1955
The University of Sydney
Page 20
Reference: On the history of the transportation and maximum flow problems. Alexander Schrijver in Math Programming, 91: 3, 2002.

Maximum Flow and Minimum Cut
– Max flow and min cut.
– Two very rich algorithmic problems.
– Cornerstone problems in combinatorial optimization.
– Mathematical duality.
– Nontrivial applications / reductions.
– Data mining.
– Open-pit mining.
– Project selection.
– Airline scheduling.
– Bipartite matching.
– Baseball elimination.
– Image segmentation.
– Network connectivity.
– Network reliability.
– Distributed computing.
– Egalitarian stable matching.
– Securityofstatisticaldata.
– Network intrusion detection.
– Multi-camera scene reconstruction.
– Manymanymore…
The University of Sydney
Page 21

Flow network
– Abstraction for material flowing through the edges.
– G = (V, E): a directed graph with no parallel edges.
– Two distinguished nodes: s = source, t = sink.
– The source has no incoming edges and the sink has no outgoing edges.
– c(e) = capacity of edge e. 295
10
sources 5 3 8 6
4
15 15
10
10 tsink 10
Page 22
capacity
The University of Sydney
15
46
15 4 30 7

Flows
– Definition: An s-t flow is a function that satisfies: – For each e Î E: 0 £ f(e) £ c(e)
– We say e is saturated if f(e) = c(e)
– For each v Î V – {s, t}: å f(e) =
(capacity) (conservation)
e in to v
– Definition: The value of a flow f is:
å f(e) e out of v
The University of Sydney
0
Value =Pa4ge 23
capacity 10 flow 4
0
15 15 0
v( f ) = 2 9 5
å f (e) . e out of s
0
10
4
0
10
44
s 5 3 8 6 10 t
0
04
15
0
40 6 150 0
4 30 7

Flows
– Definition: An s-t flow is a function that satisfies: – For each e Î E: 0 £ f(e) £ c(e)
– We say e is saturated if f(e) = c(e)
– For each v Î V – {s, t}: å f(e) =
(capacity) (conservation)
e in to v
– Definition: The value of a flow f is:
å f(e) e out of v
v( f ) = 2 9 5
å f (e) . e out of s
6
10
8
6
capacity 10
15 15 0 0
44
s 5 3 8 6 10 t
flow 10 38
15
11
40 6 150 1
4 30 7
10
10
The University of Sydney
11
Value =P2ag4e 24

Maximum Flow Problem
– Max flow problem. Find s-t flow of maximum value.
– Question: How to characterize optimal solution?
– DP and D&C uses a recurrence equation. Not known if max flows admit such a recurrence.
2 9 5
9
capacity 10
15 15 0 1
9
10
9
40
s 5 3 8 6 10 t
flow 10 48
15
14
40 6 150 4
4 30 7
10
10
The University of Sydney
14
Value =P2ag8e 25

Characterizing Max Flow
Simple conditions implying f is a max flow: – f saturates every edge out of s OR
– f saturates every edge out of t
2 9 5
9
capacity 10
15 15 0 1
9
10
9
40
s 5 3 8 6 10 t
flow 10 48
15
14
40 6 150 4
4 30 7
10
10
The University of Sydney
14
Value =P2ag8e 26

Cuts
Definitions:
– Ans-tcutisapartition(A,B)ofVwithsÎAandtÎB.
cap(A,B) = – Only count capacity of outgoing edges!
å c(e) e out of A
– The capacity of a cut (A, B) is: 295
10
4
15 15
10
s 5 3 8 6 10 t A
15
46
10
15 4 30 7
Capacity = 10 + 5 + 15
The University of Sydney
= 30
Page 27

Cuts
Definitions:
– Ans-tcutisapartition(A,B)ofVwithsÎAandtÎB.
å c(e) e out of A
cap(A,B) = – Only count capacity of outgoing edges!
– The capacity of a cut (A, B) is:
2 9 5
10
15 15
s 5 3 8 6 10 t
4
10
A
The University of Sydney
15 4 30 7
15
46
10
Capacity = 9 + 15 + 8 + 30
= 62
Page 28

Minimum Cut Problem
Min s-t cut problem:
Find an s-t cut of minimum capacity.
– Question: How to characterize optimal solution?
– Not known if min cuts admit a DP-style recurrence.
2 9 5
10
4
15
s 5 3 8 6 10 t
15
10
A
The University of Sydney
15
46
4 30 7
10
15
Capacity = 10 + 8 + 10
= 28
Page 29

Max-Flow = Min-Cut
1. Max-Flow ≤ Min-Cut
2. AlgorithmforMax-Flowfindsaflowfandacut(A,B)such that v(f) = cap(A,B)
2 9 5
9
capacity 10
15 15 0 1
9
10
9
40
s 5 3 8 6 10 t
flow 10 48
15
14
40 6 150 4
4 30 7
10
10
The University of Sydney
14
Value =P2ag8e 30

Notation
– Given a vertex u, define fout(u) = total flow on edges leaving u
– Given a vertex subset S, define fout(S) = total flow on edges leaving S
– Similarly, define fin(u) and fin(S) on edges entering u and S, resp.
– Can rewrite v(f) = fout(s) and fin(u) = fout(u) for v not s,t
6
2 9 5
10
10
44
0
15 15 0
6
10
388
s 5 3 8 6 10 t
The University of Sydney
4 30 7
A
1
40 6 150
11
10
10
15
11
Value = 10+3+11 = 24Page 31

Flows and Cuts
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
v(f) = fout(A) – fin(A)
6
2 9 5
10
10
44
0
15 15 0
6
10
388
s 5 3 8 6 10 t
A
1
40 6 150
11
10
10
15
11
Value = 10+3+11 = 24Page 34
The University of Sydney
4 30 7

Flows and Cuts
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
v(f) = fout(A) – fin(A) 6
The University of Sydney
7
Value = 6 + 0 + 8 – 1 + 11 = 24 Page 35
A
1
40 6 150
10
10
10
10
44
0
15 15 0
6
10
2 9 5
388
s 5 3 8 6 10 t
15
11
11
4 30

Flows and Cuts
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
v(f) = fout(A) – fin(A) 6
2 9 5
10
10
44
0
15 15 0
6
10
388
s 5 3 8 6 10 t
A
1
40 6 150
10
10
15
11
11
4 30
The University of Sydney
7
Value = 10 – 4 + 8 – 0 + 10 = 24 Page 36

Proof of flow value lemma
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
Proof:
v(f) = fout(A) – fin(A)
v(f) = fout(s) = fout(s) – fin(s)
The University of Sydney
Page 37
by flow conservation, all terms except v = s are 0, i.e. fout(v) – fin(v) = 0
= S (fout(v) – fin(v)) vÎA
=S f(e)–Sf(e)
e out of A
e into A = fout(A) – fin(A)

Flows and Cuts
– Weak duality. Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut, i.e.
v(f) ≤ cap(A, B)
Cut capacity = 30 Þ Flow value £ 30 2 9 5
10
4
15 15
10
s 5 3 8 6 10 t A
15
46
10
15 4 30 7
The University of Sydney
Capacity = P3ag0e 39

Flows and Cuts
– Weak duality. Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut, i.e.
v(f) ≤ cap(A, B)
Cut capacity = 28 Þ Flow value £ 28 2 9 5
10
4
15 15
10
s 5 3 8 6 10 t A
15 4 30 7
15
46
10
The University of Sydney
Capacity = P2ag8e 40

Flows and Cuts
Weak duality. Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut, i.e.,
Proof:
v(f) = ≤ =
≤ =
fout(A) – fin(A)
fout(A)
S f(e) e out
of A
Sc(e) e out
of A c(A,B)
A
8
B
t
The University of Sydney
Page 41
v(f) £ cap(A, B).
s
7
6
4

Certificate of Optimality
Corollary: Let f be any flow, and let (A, B) be any cut.
If v(f) = cap(A, B) then f is a max flow and (A, B) is a min cut.
Value of flow = 28
Cut capacity = 28 Þ Flow value £ 28
9
2 9 5
10
10
1
15 15 0
9
10
40 489
s 5 3 8 6 10 t
4
A 15 40 6 150
10
10
The University of Sydney
4 30 7
Page 42
14
14

Summary (so far)
The University of Sydney
Page 43
1. Max flow problem
2. Min cut problem
3. Theorem: Max flow ≤ Min cut

Towards a Max Flow Algorithm
Greedy algorithm.
– Startwithf(e)=0foralledgeeÎE.
– Find an s-t path P where each edge has f(e) < c(e). – Augment flow as much flow as possible along path P. – Repeat until you get stuck. 1 00 20 10 s 300 t 10 20 00 Flow value = 0 The University of Sydney Page 44 2 Towards a Max Flow Algorithm Greedy algorithm. – Startwithf(e)=0foralledgeeÎE. – Find an s-t path P where each edge has f(e) < c(e). – Augment as much flow as possible along path P. – Repeat until you get stuck. 1 s s 3 0 X0 2 0 t t 20 X0 20 0 10 10 0 20 X0 2 0 Flow value = 20 The University of Sydney Page 45 2 Towards a Max Flow Algorithm Augmenting greedy flow to get optimal flow 11 20 0 20 10 20 10 20 10 s 3020 t s 3010 t 10 20 10 20 0 20 10 20 22 TgherUeniverdsityof=Syd2ne0y opt = 30 Page 46 Towards a Max Flow Algorithm Augmenting greedy flow to get optimal flow – Send 10 units on (s,2) edge 11 20 0 20 10 20 10 20 10 s 3020 t s 3010 t 10 20 10 20 10 20 10 20 22 TgherUeniverdsityof=Syd2ne0y opt = 30 Page 47 Towards a Max Flow Algorithm Augmenting greedy flow to get optimal flow – Send 10 units on (s,2) edge – “Undo” 10 units on (1,2) edge to preserve conservation at vertex 2 11 20 0 20 10 20 10 20 10 s 3010 t s 3010 t 10 20 10 20 10 20 10 20 22 TgherUeniverdsityof=Syd2ne0y opt = 30 Page 48 Towards a Max Flow Algorithm Augmenting greedy flow to get optimal flow – Send 10 units on (s,2) edge – “Undo” 10 units on (1,2) edge to preserve conservation at vertex 2 – Send 10 units on (1,t) edge to preserve conservation at vertex 1 11 20 10 20 10 20 10 20 10 s 3010 t s 3010 t 10 20 10 20 10 20 10 20 22 TgherUeniverdsityof=Syd2ne0y opt = 30 Page 49 Build a Residual Graph Gf = (V, Ef ) – Original edge: e = (u, v) Î E. – Flowf(e),capacityc(e). – Residualedge. – e=(u,v)andeR =(v,u). capacity u 17 v 6 flow residual capacity u 11 v – IfeinE,theneisa“forward”edge,else“backward”edge – Residualcapacity: cf(e)=ìíc(e)-f(e) ifeÎE îf(e) if eR ÎE – Residual graph: Gf = (V, Ef ). – Residualedgeswithpositiveresidualcapacity. 6 – Residualcapacityofforwardedgeerepresentssparecapacityofe – ResidualcapacityofbackwardedgeeRrepresentscurrentflowonethat – Ef ={e:f(e)0}.
– MaxflowofGf=(MaxflowofG)–v(f)(Exercise)
The University of Sydney Page 50
residualcapacity

Augmenting Path Algorithm
Notations:
P = a simple s-t path in Gf
bottleneck(P,f) = minimum residual capacity of any edge on P with respect to the current flow f.
u 20
G
s
10
10 30
t 20
v
u 10 Gf 20
s 30 10
v
t 20
The University of Sydney
Page 52

Augmenting Path Algorithm
Notations:
P = a simple s-t path in Gf
bottleneck(P,f) = minimum residual capacity of any edge on P with respect to the current flow f.
0/10
s
v
u 20/30
G
20/20 s
0/10
t 20/20
v
u Gf
t
The University of Sydney
Page 53

Augmenting Path Algorithm
Notations:
P = a simple s-t path in Gf
bottleneck(P,f) = minimum residual capacity of any edge on P with respect to the current flow f.
u 20/30
G
t 20/20
u Gf 10
Augment(f,P) {
b ¬ bottleneck(P,f) foreach e =(u,v) Î P {
if e is a forward edge then
increase f(e) in G by b
else (e is a backward edge)
decrease f(e) in G by b
}
return f }
20/20 s
0/10
v
0/10
20
s 10
v bottleneck
20 10
t 20
The University of Sydney
Page 55

Augmenting Path Algorithm
Notations:
P = a simple s-t path in Gf
bottleneck(P,f) = minimum residual capacity of any edge on P with respect to the current flow f.
The University of Sydney
u s 10/30
G
Augment(f,P) {
b ¬ bottleneck(P,f) foreach e =(u,v) Î P {
if e is a forward edge then
increase f(e) in G by b
else (e is a backward edge)
decrease f(e) in G by b
}
return f }
20/20
t
10/10
10/10
v
u Gf 10
20/20
20
s 10
v
Augment(f,P) gives a new flow f’ in G with v(f’) = b + v(f) Page 56
20 10
t 20

Augmenting Path Algorithm
Ford-Fulkerson(G,s,t) { foreach e Î E
f(e) ¬ 0
Gf ¬ residual graph
while (there exists augmenting path P in Gf){ f ¬ Augment(f,P)
update Gf }
return f }
Augment(f,P) {
b ¬ bottleneck(P,f) foreach e =(u,v) Î P {
if e is a forward edge then
increase f(e) in G by b
else (e is a backward edge)
decrease f(e) in G by b
}
return f }
Page 57
The University of Sydney

Ford-Fulkerson Algorithm
244
10 2 8 6 10
s 10 3 9 5 10 t
G:
capacity
The University of Sydney Page 58

Ford-Fulkerson Algorithm
0
2 4 4
flow
capacity
G:
s 10 3 9 5 10 t
0 10208 6010
00 000
The University of Sydney
Page 59
Flow value = 0

Ford-Fulkerson Algorithm
0
2 4 4
flow
capacity
G:
s 10 3 9 5 10 t
0 10208 6010
8X0 0 X8
0 0 8X0
Flow value = 0
244
residual capacity 10
Gf:
10
2
86
s 10 3 9 5 10 t
The University of Sydney
Page 60

Ford-Fulkerson Algorithm
G:
0
2 4 4
1 0 X8 8
10208 6010
s 10 3 X 5 t 9 10
X
0 2 02 10X8
0
2 4 4
Flow value = 8
Gf:
8
2
86
10
2 s 10 3
9 5 2 t 8
The University of Sydney
Page 61

Ford-Fulkerson Algorithm
G:
0
2 4 4
X0 6 1022 X10
X06
s 10 3 X 5
2 4 4
10 2 8 6 10
10 8
860
28
9 10
t
Flow value = 10
6 10
Gf:
s 10 3 7 5 10 t 2
The University of Sydney
Page 62

Ford-Fulkerson Algorithm
2 4 4
02 X
G:
s 10 3 9 5 10 t
X6 8 10 22 8 66 10
10 8 X0
X68 8 10
Flow value = 16
Gf:
2 4 4
10 2 8 6 4
6
s 4 3 1 5 10 t
The University of Sydney
Page 63
6
8

Ford-Fulkerson Algorithm
G:
23 X
2 4 4
X8 9 10 20 8 66 10
10 87 X
X8 9 8 9 1 0 s 10 3 X 5
t
Flow value = 18
8
9 10
Gf:
2
2 2 4
10 2 8 6 2
s 2 3 1 5 10 t
The University of Sydney
Page 64
8
8

Ford-Fulkerson Algorithm
3
2 4 4
G:
s 10 3 9 5 10 t
9 10 20 8 66 10
10 7
9 9 10
3
2 1 4
Gf: 1 9
Flow value = 19
10 2 7
6 1
s 1 3 9 5 10 t 9
The University of Sydney
Page 65

Ford-Fulkerson Algorithm
G:
3
2 4 4
9 10 20 8 66 10
10 7
9 9 10
s 10 3 9 5 10 t
Cut capacity = 19 Flow value = 19
3
2 1 4
Gf: 1 9
The University of Sydney
Page 66
10 2 7
s 1 3 9 9
6 1
5 10 t

Max-Flow Min-Cut Theorem
Augmenting path theorem: Flow f is a max flow if and only if there are no augmenting paths.
Max-flow min-cut theorem: The value of the max flow is equal to the value of the min cut. [Ford-Fulkerson 1956]
Proof strategy: We prove both simultaneously. Let f be a flow. Then the following are equivalent:
(i) There exists a cut (A, B) such that v(f) = cap(A, B). (ii) Flow f is a max flow.
(iii) There is no augmenting path relative to f.
– (i) Þ (ii) This was the corollary to the weak duality lemma.
– (ii) Þ (iii) We show contrapositive.
– Letfbeaflow.Ifthereexistsanaugmentingpath,thenwecanimprovef
by sending flow along a path P and augment the flow in G.
The University of Sydney Page 68

Proof of Max-Flow Min-Cut Theorem
– (iii) Þ (i)
– Let f be a flow with no augmenting paths.
– Let A be set of vertices reachable from s in residual graph. – BydefinitionofA,sÎA.
– Bydefinitionoff,tÏA.
v(f)= X f(e) X f(e) e out of A e into A
A
B
t
s
The University of Sydney
original network
Page 69

Proof of Max-Flow Min-Cut Theorem
– (iii) Þ (i)
– Let f be a flow with no augmenting paths.
– Let A be set of vertices reachable from s in residual graph. – BydefinitionofA,sÎA.
– Bydefinitionoff,tÏA.
v(f)= X f(e) X f(e) e out of A e into A
A
B
t
No augmenting path from A to B => every edge leaving A saturated, every edge entering A is empty
s
The University of Sydney
original network
Page 70

Proof of Max-Flow Min-Cut Theorem
– (iii) Þ (i)
– Let f be a flow with no augmenting paths.
– Let A be set of vertices reachable from s in residual graph. – BydefinitionofA,sÎA.
– Bydefinitionoff,tÏA.
v(f)= X f(e) X f(e) e out of A e into A
= c(e) e out of a
= cap(A, B)
No augmenting path from A to B => every edge leaving A saturated, every edge entering A is empty
A
B
t
s
The University of Sydney
original network
Page 71

Max-Flow Min-Cut Theorem
Augmenting path theorem: Flow f is a max flow if and only if there are no augmenting paths.
Max-flow min-cut theorem: The value of the max flow is equal to the value of the min cut. [Ford-Fulkerson 1956]
Proof strategy: We prove both simultaneously. Let f be a flow. Then the following are equivalent:
(i) There exists a cut (A, B) such that v(f) = cap(A, B). (ii) Flow f is a max flow.
(iii) There is no augmenting path relative to f.
Note: This implies we can check if a given flow f is max flow in time O(n + m)!
The University of Sydney Page 72

Ford-Fulkerson: Analysis
Assumption. All initial capacities are integers.
Lemma. At every intermediate stage of the Ford-Fulkerson algorithm
the flow values and the residual graph capacities in Gf are integers.
Proof: (proof by induction)
Base case: Initially the statement is correct. Induction hyp.: True after j iterations.
Induction step: Since all the residual capacities in Gf are integers the bottleneck-value must be an integer. Thus the flow will have integer values and hence also the capacities in the new residual graph.
Integrality theorem. If all capacities are integers, then there exists a max flow f for which every flow value f(e) is an integer.
The University of Sydney Page 73

Ford-Fulkerson: Running Time
Observation:
Let f be a flow in G, and let P be a simple s-t path in Gf. v(f’) = v(f) + bottleneck(f,P)
and since bottleneck(f,P)>0 v(f’) > v(f).
Þ The flow value strictly increases in an augmentation
Theorem. The algorithm terminates in at most v(fmax) £ F iterations, where F = value of max flow.
Proof: Each augmentation increase flow value by at least 1.
The University of Sydney Page 74

Ford-Fulkerson: Running Time
Corollary:
Ford-Fulkerson runs in O((m+n)F) time, if all capacities are integers.
Proof: C iterations.
Path in Gf can be found in O(m+n) time using BFS. Augment(P,f) takes O(n) time.
Updating Gf takes O(n) time.
The University of Sydney
Page 75

7.3 Choosing Good Augmenting Paths
Is O(F(m+n)) a good time bound?
• Yes, if F is small.
• If F is large, can the number of iterations be as bad as F?
The University of Sydney Page 76

Ford-Fulkerson: Exponential Number of Augmentations
Question: Is generic Ford-Fulkerson algorithm polynomial in
input size?
Answer: No. If max capacity is D, then algorithm can take D iterations.
1
1X0 0
DD
s 1X01 t
m, n, and log C
D
D
00 X1
2
The University of Sydney
Page 77

Ford-Fulkerson: Exponential Number of Augmentations
Question: Is generic Ford-Fulkerson algorithm polynomial in
input size?
Answer: No. If max capacity is D, then algorithm can take D iterations.
11
1 X0 0 1 X0 X0 1 DDDD
s 1X01 t s 1X0X10 t DDDD
0 0 10 X01 X1X
m, n, and log C
22
The University of Sydney
Page 78

Choosing Good Augmenting Paths
– Use care when selecting augmenting paths.
– Some choices lead to exponential algorithms.
– Clever choices lead to polynomial algorithms.
– If capacities are irrational, algorithm not guaranteed to terminate!
– Goal: choose augmenting paths so that: – Can find augmenting paths efficiently.
– Few iterations.
– Choose augmenting paths with: [Edmonds-Karp 1972, Dinitz 1970] – Max bottleneck capacity.
– Sufficiently large bottleneck capacity.
– Fewest number of edges.
The University of Sydney Page 79

Choosing Good Augmenting Paths
– Ford Fulkerson
Choose any augmenting path (C iterations)
– Edmonds Karp #1 (m log C iterations) Choose max flow path
– Improved Ford Fulkerson via capacity scaling (log C iterations) Choose max flow path
– Edmonds Karp #2 (O(nm) iterations)
Choose minimum link path [Edmonds-Karp 1972, Dinitz 1970]
The University of Sydney Page 80

Edmonds-Karp #1
Pick the augmenting path with largest capacity [maximum bottleneck path]
The University of Sydney Page 81

Edmonds-Karp #1
Pick the augmenting path with largest capacity [maximum bottleneck path]
Claim: If maximum flow in G is F, there must exists a path from s to t with bottleneck capacity at least F/m.
Proof:
Delete all edges of capacity less than F/m.
Is the graph still connected?
Yes, otherwise we have a cut of value less than F.
A
B
t
< F/m s The University of Sydney < F/m Page 84 Edmonds-Karp #1 Pick the augmenting path with largest capacity [maximum bottleneck path] Claim: If maximum flow in residual graph Gf is F, there must exists a path from s to t with bottleneck capacity at least F/m. Proof: Delete all edges of capacity less than F/m. Is the graph still connected? Yes, otherwise we have a cut of value less than F. A B t < F/m s The University of Sydney < F/m Page 85 Edmonds-Karp #1 Theorem: Edmonds-Karp #1 makes at most O(m log F) iterations. Proof: At least 1/m of remaining flow is added in each iteration. Û Remaining flow reduced by a factor of (1-1/m) per iteration. #iterations until remaining flow <1? Þ F×(1-1/m)x <1? We know: (1-1/m)m < 1/e Set x = m ln F Þ F × (1-1/m)m ln F < F × (1/e)ln F = 1 The University of Sydney Page 88 Applications The University of Sydney Page 89 – Bipartite matching – Perfect matching – Disjoint paths – Network connectivity – Circulation problems – Image segmentation – Baseball elimination – Project selection Summary The University of Sydney Page 90 1. 2. 3. 4. 5. Max flow problem Min cut problem Ford-Fulkerson: 1. Residual graph 2. correctness 3. complexity Max-Flow Min-Cut theorem Edmonds-Karp Appendix: Proof of Flow Value Lemma by Induction tz f Flow conservation Flowvaluelemmacziven flow f f fg fg f 174 finfu FOH f sforetCA Pt by induction on IAI Inductive case A I Let u c Aks The University of Sydney Page 91 Equiv WTS f want f UtfAl u3 fin fat A fin A fat CA fo't'CAl a3 Alfie finCA finCA cut A B fatCA fin A fztfz re f fout EB finS3 s to A 1243 O Inc in fin 4 11 Increase in fo

Related Posts