Quiz Summary
The University of Sydney
Page 1
Quiz 3 Assignment 3
Fri 1 November 2019 (Week 12) Sun 3 November 2019, 11:59PM
Dynamic Programming Summary
1D dynamic programming
Weighted interval scheduling
Segmented Least Squares
Maximum-sum contiguous subarray Longest increasing subsequence
2D dynamic programming Knapsack
Longest common subsequence Shortest path
Dynamic programming over intervals
RNA Secondary Structure The University of Sydney
Not Examined
Page 2
Flow networks I
The University of Sydney
Page 3
Soviet Rail Network, 1955
The University of Sydney
Page 4
Reference: On the history of the transportation and maximum flow problems. Alexander Schrijver in Math Programming, 91: 3, 2002.
4
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 5
Minimum Cut Problem
Flow network
Abstraction for material flowing through the edges. G = (V, E) = directed graph, no parallel edges.
Two distinguished nodes: s = source, t = sink.
c(e) = capacity of edge e.
295
10
15 15
sources 5 3 8 6 10 tsink
4
10
capacity
The University of Sydney
Page 6
15
46
10
15 4 30 7
Cuts
Definitions:
Ans-tcutisapartition(A,B)ofVwithsIAandtIB.
The capacity of a cut (A, B) is: cap(A, B) = 295
a c(e) e out of A
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 7
Cuts
Definitions:
Ans-tcutisapartition(A,B)ofVwithsIAandtIB.
The capacity of a cut (A, B) is: cap(A, B) = 2 9 5
10
a c(e) e out of A
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 8
Minimum Cut Problem
Min s-t cut problem:
Find an s-t cut of minimum capacity.
295
10
15 15
sources 5 3 8 6 10 tsink
4
10
15
46
10
15 4 30 7
The University of Sydney
Page 9
Minimum Cut Problem
Min s-t cut problem:
Find an s-t cut of minimum capacity.
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 10
Flows
Definition: An s-t flow is a function that satisfies: For each e I E: 0 f(e) c(e)
(capacity) (conservation)
For each v I V {s, t}: a f(e) = e in to v
Definition: The value of a flow f is: 0
a f (e) . e out of s
0
10
a f(e) e out of v
v( f ) = 2 9 5
4
10
0
15 15 0
44 044
s 5 3 8 6 10 t
capacity
flow
15
0
0
40 6 150
0
0
10
The University of Sydney
4 30 7
Value =Pa4ge 11
Flows
Definition: An s-t flow is a function that satisfies: For each e I E: 0 f(e) c(e)
(capacity) (conservation)
For each v I V {s, t}: a f(e) = e in to v
Definition: The value of a flow f is: 6
a f (e) . e out of s
6
10
a f(e) e out of v
v( f ) = 2 9 5
10
10
0
15 15 0
44 388
s 5 3 8 6 10 t
capacity
flow
15
11
1
40 6 150
11
10
10
The University of Sydney
4 30 7
Value =P2ag4e 12
Maximum Flow Problem
Max flow problem. Find s-t flow of maximum value.
9
2 9 5
10
10
1
15 15 0
9
10
40 489
s 5 3 8 6 10 t
capacity
flow
15
14
4
40 6 150
14
10
10
The University of Sydney
4 30 7
Value =P2ag8e 13
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.
af(e) af(e) = v(f) e out of A e in to A
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
Value =P2ag4e 14
A
1
40 6 150
11
10
10
15
11
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.
af(e) af(e) = v(f) e out of A e in to 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 = 6 + 0 + 8 1 + 11 = 24 Page 15
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.
af(e) af(e) = v(f) e out of A e in to 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 4 + 8 0 + 10 = 24 Page 16
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.
Proof:
by flow conservation, all terms except v = s are 0 i.e. fout(v) fin(v) = 0
The University of Sydney
af(e) af(e) = v(f) e out of A e in to A
v(f)= af(e) e out of s
= a a f(e) a f(e)o
v IA
ce
e out of v e in to v
= af(e)- af(e). e out of A e in to A
Page 17
Flows and Cuts
Flow value cut. 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.
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 18
Flows and Cuts
Max flow value cut (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 (v(f) cap(A, B)).
Proof: v(f) =
a f(e)- a f(e)
e out of A
a f(e)
a c(e) e out of A
e in to A
= cap(A,B)
A
4
8
7
6
B
t
e out of A
s
The University of Sydney
Page 19
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 20
14
14
Towards a Max Flow Algorithm
Greedy algorithm.
Startwithf(e)=0foralledgeeIE.
Find an s-t path P where each edge has f(e) < c(e). Augment flow along path P. Repeat until you get stuck. 10020 10s 300 t10 2000Flow value = 0 The University of SydneyPage 212 Towards a Max Flow AlgorithmGreedy algorithm. Startwithf(e)=0foralledgeeIE. Find an s-t path P where each edge has f(e) < c(e). Augment flow along path P. Repeat until you get stuck. 1 s s3 0 X0 2 0t t20 X02001010020X0 2 0Flow value = 20 The University of SydneyPage 222 Towards a Max Flow AlgorithmGreedy algorithm. Startwithf(e)=0foralledgeeIE. Find an s-t path P where each edge has f(e) < c(e). Augment flow along path P. Repeat until you get stuck.1120 0 20 1020 10 20 10s 3020 t s 3010 t10 20 10 200 20 10 2022TgherUeniverdsityof=Syd2ne0y opt = 30 Page 23 Residual Graph Originaledge: e=(u,v) IE. Flowf(e),capacityc(e). Residualedge. “Undo”flowsent. e=(u,v)andeR =(v,u). Residualcapacity:c(e)=iic(e)-f(e) ifeIEf i f (e) if eR I E Residual graph: Gf = (V, Ef ). Residualedgeswithpositiveresidualcapacity. Ef ={e:f(e)
capacity
u 17 v
6
flow
residualcapacity
u 11 v
6
residual capacity
The University of Sydney
Page 24
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 s 20/30
G
20/20
t
0/10
0/10
s
v
20/20
v
u Gf
t
The University of Sydney
Page 25
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 s 20/30
G
20/20
t
0/10
0/10
v
u Gf 10
20/20
20
s 10
v
20 10
t 20
The University of Sydney
Page 26
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 s 20/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
0/10
0/10
v
u Gf 10
20/20
20
s 10
v bottleneck
20 10
t 20
The University of Sydney
Page 27
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 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
20 10
t 20
The University of Sydney
Page 28
Augment(f,P) gives a new flow f in G
Ford-Fulkerson Algorithm
Ford-Fulkerson(G, s, t) { foreache I E f(e) 0 Gf residual graph
while (there exists augmenting path P) {
f Augment(f, P)
update Gf }
return f }
Augment(f, P) {
b bottleneck(P) foreach e I P {
if(e I E)f(e) f(e)+b
else f(eR) f(e) b }
return f }
The University of Sydney
Page 29
forward edge reverse edge
Ford-Fulkerson Algorithm
244
10 2 8 6 10
s 10 3 9 5 10 t
G:
capacity
The University of Sydney Page 30
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 31
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 32
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 33
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 34
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 35
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 36
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 37
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
Cut capacity = 19 Flow value = 19
3
2 1 4
Gf: 1 9
10 2 7
6 1
s 1 3 9 5 10 t 9
The University of Sydney
Page 38
Augmenting Path Algorithm
Ford-Fulkerson(G, s, t) { foreache I E f(e) 0 Gf residual graph
while (there exists augmenting path P) {
f Augment(f, P)
update Gf }
return f }
Augment(f, P) {
b bottleneck(P) foreach e I P {
if(e I E)f(e) f(e)+b
else f(eR) f(e) b }
return f }
The University of Sydney
Page 39
forward edge reverse edge
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.
(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 weak duality (flow value cut) lemma.
(ii) (iii) We show contrapositive.
Letfbeaflow.Ifthereexistsanaugmentingpath,thenwecanimprovef
by sending flow along path.
The University of Sydney Page 40
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,sIA.
Bydefinitionoff,tIA.
v(f) = =
af(e)- af(e)
e out of A
a c(e)
e in to A
A
B
e out of A
= cap(A,B)
t
s
The University of Sydney
original network
Page 41
Running Time
Assumption. All capacities are integers between 1 and C.
Invariant. Every flow value f(e) and every residual capacities cf (e) remains an
integer throughout the algorithm.
Theorem. The algorithm terminates in at most v(f*) nC augmenting paths, where f* is a max flow.
Proof: Each augmentation increase value by at least 1.
Corollary. The running time of FordFulkerson is O(m n C). If C = 1, Ford-
Fulkerson runs in O(mn) time.
Proof: Can use either BFS or DFS to find an augmenting path in O(m) time.
Integrality theorem. If all capacities are integers, then there exists a max flow f for which every flow value f(e) is an integer.
Proof: Since algorithm terminates, theorem follows from invariant.
The University of Sydney Page 42
Choosing Good Augmenting Paths
The University of Sydney Page 44
Ford-Fulkerson: Exponential Number of Augmentations
Question: Is generic Ford-Fulkerson algorithm polynomial in
input size?
Answer: No. If max capacity is C, then algorithm can take C iterations.
11
1 X0 0 1 X0 X0 1
CCCC
s 1X01 t s 1X0X10 t
CCCC
0 0 10 X01 X1X
m, n, and C
22
The University of Sydney
Page 45
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 46
Capacity Scaling
Intuition. Choosing path with highest bottleneck capacity increases flow by max possible amount.
Dont worry about finding exact highest bottleneck path.
Maintain scaling parameter D.
Let Gf (D) be the subgraph of the residual graph consisting of only arcs with capacity at least D.
44
110 102
110 102
s1ts t 122 170 122 170
22
Gf Gf (100)
The University of Sydney
Page 47
Capacity Scaling
Scaling-Max-Flow(G, s, t) { foreache I E f(e) 0
D smallest power of 2 greater than or equal to C Gf residual graph
while (D 3 1) {
Gf(D) D-residual graph
while (there exists augmenting path P in Gf(D)) {
f augment(f, P)
update Gf(D) }
DD/2 }
return f }
The University of Sydney Page 48
Capacity Scaling: Correctness
Assumption. All edge capacities are integers between 1 and C. Integrality invariant. All flow and residual capacity values are
integral.
Correctness. If the algorithm terminates, then f is a max flow.
Proof:
By integrality invariant, when D = 1 Gf(D) = Gf.
Upon termination of D = 1 phase, there are no augmenting paths.
The University of Sydney Page 49
Capacity Scaling: Running Time
Lemma 1. The outer while loop repeats 1 + elog2 Cu times. Proof: Initially C D < 2C. D decreases by a factor of 2 eachiteration. Lemma 2. Let f be the flow at the end of a D-scaling phase.Then the value of the maximum flow is at most v(f) + m D.proof on next slideLemma 3. There are at most 2m augmentations per scaling phase. Let f be the flow at the end of the previous scaling phase. Lemma2 v(f*) v(f)+m(2D). Each augmentation in a D-phase increases v(f) by at least D. Theorem. The scaling max-flow algorithm finds a max flow in O(m log C) augmentations. It can be implemented to run in O(m2 log C) time. The University of SydneyPage 50Capacity Scaling: Running Time Lemma 2. Let f be the flow at the end of a D-scaling phase. Then value of the maximum flow is at most v(f) + m D. Pf. (almost identical to proof of max-flow min-cut theorem) We show that at the end of a D-phase, there exists a cut (A, B) such thatcap(A, B) v(f) + m D. Choose A to be the set of nodes reachable from s in Gf(D). BydefinitionofA,sIA. Bydefinitionoff,tIA.v(f) = a f(e)- a f(e)e out of A e in to A3 a(c(e)-D)-aDe out of A e in to A= ac(e)-aD-aDAB t e out of A e out of A 3 cap(A, B) – mDe in to AsThe University of SydneyPage 51original networkNot Examined ApplicationsThe University of SydneyPage 52 Bipartite matching Perfect matching Disjoint paths Network connectivity Image segmentation Circulation problems Bipartite MatchingThe University of Sydney Page 53 Matching Input: undirected graph G = (V, E). M I E is a matching if each node appears in at most one edgein M. Max matching: find a max cardinality matching.The University of Sydney Page 54 Bipartite Matching Input: undirected, bipartite graph G = (L E R, E). M I E is a matching if each node appears in at most one edgein M. Max matching: find a max cardinality matching.1 1′ 2 2’3 3′ 4 4’L5 5’R matching 1-2′, 3-1′, 4-5′ The University of SydneyPage 55 Bipartite Matching Input: undirected, bipartite graph G = (L E R, E). M I E is a matching if each node appears in at most one edgein M. Max matching: find a max cardinality matching.1 1′ 2 2’3 3′ 4 4’L5 5’R max matching 1-1′, 2-2′, 3-3′ 5-5′ The University of SydneyPage 56 Bipartite MatchingMax flow formulation. Create digraph G’ = (L E RE {s, t}, E’ ). Direct all edges from L to R, and assign infinite (or unit) capacity. Add source s, and unit capacity edges from s to each node in L. Add sink t, and unit capacity edges from each node in R to t. G’11 1′ 2 2’3 3′ 4 4’1stThe University of SydneyL 5 5′ RPage 57Bipartite Matching: Proof of CorrectnessTheorem: Max cardinality matching in G U value of max flow in G’. Proof: Given max matching M of cardinality k. Consider flow f that sends 1 unit along each of k paths. f is a flow, and has cardinality k.1 1′ 11’2 2′ 12 2’1G3 3’s33’tG’ 4 4′ 4 4′ The Univers5ity of Sydney 5′ 5 5′ Page 58 Bipartite Matching: Proof of CorrectnessTheorem: Max cardinality matching in G U value of max flow in G’. Proof: U LetfbeamaxflowinG’ofvaluek. Integrality theorem k is integral and can assume f is 0-1. ConsiderM=setofedgesfromLtoRwithf(e)=1. each node in L and R participates in at most one edge in M |M|=k: considercut(LEs,REt) 11′ 1 1′ 12 2’1 2 2’s 3 3′ t 3 3′ 4 4′ 4 4’G’5 5′ 5 5’G The University of Sydney Page 59 Perfect MatchingDefinition: A matching M I E is perfect if each node appears in exactly one edge in M.Question: When does a bipartite graph have a perfect matching?Structure of bipartite graphs with perfect matchings. Clearly we must have |L| = |R|.The University of SydneyPage 60 Perfect MatchingNotation: Let S be a subset of nodes, and let N(S) be the set of nodes adjacent to nodes in S.Observation. If a bipartite graph G = (L E R, E), has a perfect matching, then |N(S)| 3 |S| for all subsets S I L.Proof: Each node in S has to be matched to a different node in N(S).1 1’2 2’3 3’4 4′ No perfect matching: S = { 2, 4, 5 }N(S) = { 2′, 5′ }.The University of Sydney L 5 5′ R Page 61 Marriage TheoremMarriage Theorem. Let G = (L E R, E) be a bipartite graph with |L| = |R|. Then, G has a perfect matching iff |N(S)| 3 |S| for all subsets S I L. [Frobenius 1917, Hall 1935] Proof: This was the previous observation.1 1’2 2’3 3’4 4′ No perfect matching: S = { 2, 4, 5 }N(S) = { 2′, 5′ }.The University of Sydney L 5 5′ R Page 62Proof of Marriage Theorem Proof: U Suppose G does not have a perfect matching. Formulate as a max flow problem and let (A, B) be min cut in G’. Bymax-flowmin-cut,cap(A,B)<|L|. DefineLA =LCA, LB =LCB, RA =RCA. cap(A,B) = |LB|+|RA|. Since min cut can’t use edges: N(LA) I RA. |N(LA)||RA| = cap(A,B)-|LB| < |L|-|LB| = |LA|. ChooseS=LA. 1G’ 113’4′ t LA = {2, 4, 5} LB = {1, 3}RA = {2′, 5′} N(LA) = {2′, 5′}A21’2’1 s43The University of Sydney55’1Page 63Not Examined Bipartite Matching: Running TimeWhich max flow algorithm to use for bipartite matching? Generic augmenting path: O(mC) = O(mn). Capacity scaling: O(m2 log C ) = O(m2 log n). Shortest augmenting path: O(m n1/2).Non-bipartite matching. Structure of non-bipartite graphs is more complicated, butwell-understood. Blossom algorithm: O(n4). Best known: O(m n1/2).[Tutte-Berge, Edmonds-Galai] [Edmonds 1965] [Micali-Vazirani 1980]The University of SydneyPage 64
Reviews
There are no reviews yet.