CSC373
Week 4:
Dynamic Programming (contd) Network Flow (start)
Nisarg Shah
373F19 – Nisarg Shah 1
Recap
• Dynamic Programming Basics ➢ Optimal substructure property
➢ Bellman equation
➢ Top-down (memoization) vs bottom-up implementations
• Dynamic Programming Examples ➢ Weighted interval scheduling
➢ Knapsack problem
➢ Single-source shortest paths
➢ Chain matrix product
➢ Edit distance (aka sequence alignment)
373F19 – Nisarg Shah 2
This Lecture
• Some more DP
➢ Traveling salesman problem (TSP)
• Start of network flow ➢ Problem statement
➢ Ford-Fulkerson algorithm ➢ Running time
➢ Correctness
373F19 – Nisarg Shah 3
Traveling Salesman
• Input
➢ Directed graph 𝐺 = (𝑉, 𝐸)
➢ Distance 𝑑𝑖,𝑗 is the distance from node 𝑖 to node 𝑗
• Output
➢ Minimum distance which needs to be traveled to start from some node 𝑣, visit every other node exactly once, and come back to 𝑣
o That is, the minimum cost of a Hamiltonian cycle
373F19 – Nisarg Shah 4
Traveling Salesman
• Approach
➢ Let’s start at node 𝑣1 = 1
o It’s a cycle, so the starting point does not matter
➢Want to visit the other nodes in some order, say 𝑣 ,…,𝑣
2𝑛 ➢ Total distance is 𝑑1,𝑣2 + 𝑑𝑣2,𝑣3 + ⋯ + 𝑑𝑣𝑛−1,𝑣𝑛 + 𝑑𝑣𝑛,1
o Want to minimize this distance • Naïve solution
➢ Check all possible orderings
➢ 𝑛 − 1 ! = Θ 𝑛 ⋅ 𝑛 𝑛 (Stirling’s approximation) 𝑒
373F19 – Nisarg Shah 5
Traveling Salesman
• DP Approach
➢ Consider 𝑣 (the last node before returning to 𝑣 = 1)
𝑛1
oIf𝑣 =𝑐 𝑛
• Find optimal order of visiting nodes in 2, … , 𝑛 ∖ 𝑐 ending at 𝑐
and then
• Need to keep track of the subset of nodes visited and the end node
➢ 𝑂𝑃𝑇 𝑆, 𝑐 = minimum total travel distance when starting at 1, visiting each node in 𝑆 exactly once, and ending at 𝑐 ∈ 𝑆
➢ The original answer is min𝑂𝑃𝑇 𝑆,𝑐 + 𝑑𝑐,1, where 𝑆 = {2,…,𝑛} 𝑐∈𝑆
373F19 – Nisarg Shah 6
Traveling Salesman
• DP Approach
➢ To compute 𝑂𝑃𝑇[𝑆, 𝑐], we condition over the vertex
which is visited right before 𝑐 • Bellman equation
𝑂𝑃𝑇𝑆,𝑐 = min 𝑂𝑃𝑇𝑆∖ 𝑐,𝑚 +𝑑𝑚,𝑐 𝑚∈𝑆∖ 𝑐
Finalsolution= min 𝑂𝑃𝑇 2,…,𝑛 ,𝑐 +𝑑𝑐,1 𝑐∈ 2,…,𝑛
• Time:𝑂(𝑛⋅2𝑛)calls,𝑂(𝑛)timepercall⇒𝑂 𝑛2 ⋅2𝑛 𝑛𝑛
➢ Much better than the naïve solution which has Τ 𝑒
373F19 – Nisarg Shah 7
Traveling Salesman
• Bellman equation
𝑂𝑃𝑇𝑆,𝑐 = min 𝑂𝑃𝑇𝑆∖ 𝑐,𝑚 +𝑑𝑚,𝑐
𝑚∈𝑆∖ 𝑐
Finalsolution= min 𝑂𝑃𝑇 2,…,𝑛 ,𝑐 +𝑑𝑐,1 𝑐∈ 2,…,𝑛
• Space complexity: 𝑂 𝑛 ⋅ 2𝑛
➢ But computing the optimal solution with 𝑆 = 𝑘 only requires
storingtheoptimalsolutionswith 𝑆 =𝑘−1 • Question:
➢ Using this observation, how much can we reduce the space complexity?
373F19 – Nisarg Shah 8
DP Concluding Remarks
• Key steps in designing a DP algorithm ➢ “Generalize” the problem first
o E.g. instead of computing edit distance between strings 𝑋 =
𝑥 ,…,𝑥 and 𝑌 = 𝑦 ,…,𝑦 , we compute 𝐸[𝑖,𝑗] = edit distance
1𝑚 1𝑛
between 𝑖-prefix of 𝑋 and 𝑗-prefix of 𝑌 for all (𝑖, 𝑗)
o The right generalization is often obtained by looking at the structure of the “subproblem” which must be solved optimally to get an optimal solution to the overall problem
➢ Remember the difference between DP and divide-and- conquer
➢ Sometimes you can save quite a bit of space by only storing solutions to those subproblems that you need in the future
373F19 – Nisarg Shah 9
Network Flow
373F19 – Nisarg Shah 10
Network Flow
• Input
➢ A directed graph 𝐺 = (𝑉, 𝐸) ➢ Edge capacities 𝑐 ∶ 𝐸 → R≥0 ➢ Source node 𝑠, target node 𝑡
• Output
➢ Maximum “flow” from 𝑠 to 𝑡
373F19 – Nisarg Shah 11
Network Flow
• Assumptions
➢ For simplicity, assume that…
➢ No edges enter 𝑠
➢ No edges leave 𝑡
➢ Edge capacity 𝑐(𝑒) is a non- negative integer
o Later, we’ll see what happens when 𝑐(𝑒) can be a rational number
373F19 – Nisarg Shah 12
Network Flow
• Flow
➢An 𝑠-𝑡 flow is a function 𝑓:𝐸 → R≥0
➢ Intuitively, 𝑓(𝑒) is the “amount of material” carried on edge 𝑒
373F19 – Nisarg Shah 13
Network Flow
• Constraints on flow 𝑓
1. Respecting capacities
∀𝑒∈𝐸∶0≤𝑓 𝑒 ≤𝑐(𝑒)
2. Flow conservation
Flow in = flow out at every node other than 𝑠 and 𝑡
∀𝑣∈𝑉∖ 𝑠,𝑡 ∶ σ𝑒entering𝑣 𝑓 𝑒 =σ𝑒leaving𝑣 𝑓 𝑒
Flow out at 𝑠 = flow in at 𝑡
373F19 – Nisarg Shah 14
Network Flow
• 𝑓𝑖𝑛 𝑣 = σ𝑒 entering 𝑣 𝑓 𝑒
• 𝑓𝑜𝑢𝑡 𝑣 = σ𝑒 leaving 𝑣 𝑓 𝑒
• Value of flow 𝑓 is 𝑣 𝑓 = 𝑓𝑜𝑢𝑡 𝑠 = 𝑓𝑖𝑛(𝑡)
• Restating the problem:
➢ Given a directed graph 𝐺 = (𝑉, 𝐸) with edge capacities 𝑐: 𝐸 → R≥0, find a flow 𝑓∗ with the maximum value.
373F19 – Nisarg Shah 15
First Attempt
• A natural greedy approach
1. 2.
Start from zero flow (𝑓 𝑒 = 0 for each 𝑒).
While there exists an 𝑠-𝑡 path 𝑃 in 𝐺 such that 𝑓 𝑒 < 𝑐(𝑒) for
each 𝑒 ∈ 𝑃
a. Find one such path 𝑃
b. Increase the flow on each edge 𝑒 ∈ 𝑃 by min 𝑐 𝑒 − 𝑓 𝑒 𝑒∈𝑃
• Let’s run it on an example!
373F19 - Nisarg Shah 16
First Attempt
373F19 - Nisarg Shah 17
First Attempt
373F19 - Nisarg Shah 18
First Attempt
373F19 - Nisarg Shah 19
First Attempt
373F19 - Nisarg Shah 20
First Attempt
373F19 - Nisarg Shah 21
First Attempt
373F19 - Nisarg Shah 22
First Attempt
373F19 - Nisarg Shah 23
First Attempt
• Q: Why does the simple greedy approach fail?
• A: Because once it increases the flow on an edge, it
is not allowed to decrease it.
• Need a way to “reverse” bad decisions
373F19 - Nisarg Shah 24
Reversing Bad Decisions
Suppose we start by sending But the optimal configuration requires 20 units of flow along this path 10 fewer units of flow on 𝑢 → 𝑣
uu
𝟐𝟎/20 s
0/10
0/10 𝟐𝟎/30
t
𝟐𝟎/20 𝟏𝟎/10 s 𝟏𝟎/30
t
𝟐𝟎/20 vv
𝟏𝟎/10 𝟐𝟎/20
373F19 - Nisarg Shah 25
Reversing Bad Decisions
We can essentially send a “reverse” So now we get this optimal flow flow of 10 units along 𝑣 → 𝑢
uu
𝟐𝟎/20 𝟏𝟎/10 s 𝟏𝟎𝟐𝟎/30
t
𝟐𝟎/20 𝟏𝟎/10 s 𝟏𝟎/30
t
𝟏𝟎/10 𝟐𝟎/20 vv
𝟏𝟎/10 𝟐𝟎/20
373F19 - Nisarg Shah 26
Residual Graph
• Suppose the current flow is 𝑓
• Define the residual graph 𝐺 of flow 𝑓 𝑓
➢ 𝐺 has the same vertices as 𝐺 𝑓
➢For each edge e = (𝑢,𝑣) in 𝐺, 𝐺 has at most two edges 𝑓
o Forward edge 𝑒 = (𝑢, 𝑣) with capacity 𝑐 𝑒 − 𝑓 𝑒 • We can send this much additional flow on 𝑒
o Reverse edge 𝑒𝑟𝑒𝑣 = (𝑣, 𝑢) with capacity 𝑓(𝑒)
• The maximum “reverse” flow we can send is the maximum
amount by which we can reduce flow on 𝑒, which is 𝑓(𝑒) o We only add edge of capacity > 0
373F19 – Nisarg Shah 27
Residual Graph
• Example!
Flow 𝑓 Residual graph 𝐺
uu
𝑓
20/20 0/10 𝟐𝟎 𝟏𝟎 s20/30t s𝟐𝟎𝟏𝟎t
0/10 20/20 𝟏𝟎 𝟐𝟎 vv
373F19 – Nisarg Shah 28
Augmenting Paths
• Let 𝑃 be an 𝑠-𝑡 path in the residual graph 𝐺
𝑓
• Let bottleneck(𝑃, 𝑓) be the smallest capacity across
all edges in 𝑃
• “Augment” flow 𝑓 by “sending” bottleneck 𝑃, 𝑓 units of flow along 𝑃
➢ What does it mean to send 𝑥 units of flow along 𝑃?
➢ For each forward edge 𝑒 ∈ 𝑃, increase the flow on 𝑒 by 𝑥
➢ For each reverse edge 𝑒𝑟𝑒𝑣 ∈ 𝑃, decrease the flow on 𝑒 by 𝑥
373F19 – Nisarg Shah 29
Residual Graph
• Example!
Flow 𝑓 Residual graph 𝐺
uu
𝑓
20/20 0/10 𝟐𝟎 𝟏𝟎 s20/30t s𝟐𝟎𝟏𝟎t
0/10 20/20 𝟏𝟎 𝟐𝟎 vv
Path 𝑷 → send flow = bottleneck = 10
373F19 – Nisarg Shah 30
Residual Graph
• Example!
New flow 𝑓 New residual graph 𝐺
uu
𝑓
20/20 10/10 𝟐𝟎 𝟏𝟎 s10/30t s𝟏𝟎𝟐𝟎t
10/10 20/20 𝟏𝟎 𝟐𝟎 vv
No 𝒔-𝒕 path because no outgoing edge from 𝒔
373F19 – Nisarg Shah 31
Augmenting Paths
• Let’s argue that the new flow is a valid flow • Capacity constraints (easy):
➢If we increase flow on 𝑒, we can do so by at most the capacity of forward edge 𝑒 in 𝐺 , which is 𝑐 𝑒 − 𝑓 𝑒
𝑓
o So the new flow can be at most 𝑓 𝑒 + 𝑐 𝑒 − 𝑓 𝑒 = 𝑐(𝑒)
➢If we decrease flow on 𝑒, we can do so by at most the capacity of reverse edge 𝑒𝑟𝑒𝑣 in 𝐺 , which is 𝑓 𝑒
𝑓
o So the new flow is at least 𝑓 𝑒 − 𝑓 𝑒 = 0
373F19 – Nisarg Shah 32
Augmenting Paths
• Let’s argue that the new flow is a valid flow • Flow conservation (more tricky):
➢ Each node on the path (except 𝑠 and 𝑡) has exactly two incident edges
o Both forward / both reverse ⇒ one is incoming, one is outgoing • Flow increased on both or decreased on both
o One forward, one reverse ⇒ both incoming / both outgoing • Flow increased on one but decreased on the other
o In each case, net flow remains 0
+𝑥 +𝑥 −𝑥 −𝑥 +𝑥
st
373F19 – Nisarg Shah 33
Ford-Fulkerson Algorithm
MaxFlow(𝐺):
// initialize:
Set𝑓𝑒 =0forall𝑒in𝐺
// while there is an 𝑠-𝑡 path in 𝐺 : 𝑓
While 𝑃 = FindPath(s, t,Residual(𝐺, 𝑓))!=None: 𝑓 = Augment(𝑓, 𝑃)
UpdateResidual(𝐺,𝑓)
EndWhile Return 𝑓
373F19 – Nisarg Shah 34
Ford-Fulkerson Algorithm
• Running time:
➢ #Augmentations:
o At every step, flow and capacities remain integers
oForpath𝑃in𝐺 ,bottleneck 𝑃,𝑓 >0impliesbottleneck 𝑃,𝑓 ≥1 𝑓
o Each augmentation increases flow by at least 1 o At most 𝐶 = σ𝑒 leaving 𝑠 𝑐(𝑒) augmentations
➢ Time for an augmentation:
o 𝐺 has 𝑛 vertices and at most 2𝑚 edges
o Finding an 𝑠-𝑡 path in 𝐺 takes 𝑂(𝑚 + 𝑛) time 𝑓
➢ Total time: 𝑂( 𝑚 + 𝑛 ⋅ 𝐶)
𝑓
373F19 – Nisarg Shah 35
Ford-Fulkerson Algorithm
• Total time: 𝑂( 𝑚 + 𝑛 ⋅ 𝐶)
➢ This is pseudo-polynomial time
➢ 𝐶 can be exponentially large in the input length (the number of bits required to write down the edge capacities)
➢ Note: We assumed integer capacities, but this also gives a pseudo-polynomial time algorithm for rational capacities
o Why?
• Q: Can we convert this to polynomial time?
373F19 – Nisarg Shah 36
Ford-Fulkerson Algorithm
• Q: Can we convert this to polynomial time?
➢ Not if we choose an arbitrary path in 𝐺 at each step
𝑓
➢ In the graph below, we might end up repeatedly sending 1
unit of flow across 𝑎 → 𝑏 and then reversing it
o Takes 𝑋 steps, which can be exponential in the input length
373F19 – Nisarg Shah 37
A Brief Note
• Two quantities
➢ Number of integers provided as input ➢ Total number of bits provided as input
• Running time
➢ Strongly polynomial time
o #ops polynomial in #integers but not dependent on #bits o Running time still polynomial in #bits
➢ Weakly polynomial time o #ops polynomial in #bits ➢ Pseudo-polynomial time
o #ops polynomial in the values of the input integers (i.e. polynomial in the number of “unary digits” required to write input)
373F19 – Nisarg Shah 38
Ford-Fulkerson Algorithm
• Ways to achieve polynomial time
➢ Find the shortest augmenting path using BFS o Edmonds-Karp algorithm
o Runs in 𝑂 𝑛𝑚2 operations
• “Stronglypolynomialtime” o Can be found in CLRS
➢ Find the maximum bottleneck capacity augmenting path o Runs in 𝑂 𝑚2 ⋅ log 𝐶 operations
• “Weaklypolynomialtime” ➢…
373F19 – Nisarg Shah 39
Max Flow Problem
• Race to reduce the running time
➢ 1972: 𝑂 ➢ 1980: 𝑂 ➢ 1983: 𝑂
➢ 1986: 𝑂 ➢ 1992: 𝑂
𝑛 𝑚2 Edmonds-Karp
𝑛 𝑚 log2 𝑛 Galil-Namaad
𝑛 𝑚 log 𝑛
Sleator-Tarjan
𝑛 𝑚 log 𝑛 Τ Goldberg-Tarjan
2
𝑚
𝑛 𝑚 + 𝑛2+𝜖 King-Rao-Tarjan
𝑛 𝑚 log 𝑛
➢ 1996: 𝑂 oNote:Theseare𝑂(𝑛𝑚)when𝑚=𝜔 𝑛
➢ 2013: 𝑂(𝑛 𝑚) Orlin o Breakthrough!
log 𝑚 ൗ
King-Rao-Tarjan
𝑛 log 𝑛
373F19 – Nisarg Shah 40
Back to Ford-Fulkerson
• We argued that the algorithm must terminate, and mustterminatein𝑂 𝑚+𝑛 ⋅𝐶 time
• But we didn’t argue correctness yet, i.e., the algorithm must terminate with the optimal flow
373F19 – Nisarg Shah 41
Recall: Ford-Fulkerson
MaxFlow(𝐺):
// initialize:
Set𝑓𝑒 =0forall𝑒in𝐺
// while there is an 𝑠-𝑡 path in 𝐺 : 𝑓
While 𝑃 = FindPath(s, t,Residual(𝐺, 𝑓))!=None: 𝑓 = Augment(𝑓, 𝑃)
UpdateResidual(𝐺,𝑓)
EndWhile Return 𝑓
373F19 – Nisarg Shah 42
Recall: Notation • 𝑓 = flow, 𝑠 = source, 𝑡 = target
• 𝑓𝑜𝑢𝑡,𝑓𝑖𝑛
➢ For a node 𝑢: 𝑓𝑜𝑢𝑡 𝑢 ,𝑓𝑖𝑛(𝑢) = total flow out of and into 𝑢
➢ For a set of nodes 𝑋: 𝑓𝑜𝑢𝑡 𝑋 , 𝑓𝑖𝑛(𝑋) defined similarly
• Constraints
➢Capacity:0≤𝑓 𝑒 ≤𝑐(𝑒)
➢ Flow conservation: 𝑓𝑜𝑢𝑡 𝑢 = 𝑓𝑖𝑛(𝑢) for all 𝑢 ≠ 𝑠, 𝑡
• 𝑣 𝑓 = 𝑓𝑜𝑢𝑡(𝑠) = 𝑓𝑖𝑛(𝑡) = value of the flow
373F19 – Nisarg Shah 43
Cuts and Cut Capacities
• (𝐴, 𝐵) is an 𝑠-𝑡 cut if it is a partition of vertex set 𝑉 (i.e. 𝐴 ∪ 𝐵 = 𝑉,
𝐴 ∩ 𝐵 = ∅) with 𝑠 ∈ 𝐴, and 𝑡 ∈ 𝐵
• Its capacity, denoted 𝑐𝑎𝑝 𝐴, 𝐵 , is the sum of capacities of edges leaving 𝐴
373F19 – Nisarg Shah 44
Cuts and Flows
• Theorem: For any flow 𝑓 and any 𝑠-𝑡 cut (𝐴, 𝐵), 𝑣𝑓 =𝑓𝑜𝑢𝑡 𝐴 −𝑓𝑖𝑛(𝐴)
• Proof (on the board): Just take a sum of the flow conservation constraint over all nodes in 𝐴
373F19 – Nisarg Shah 45
Cuts and Flows
• Theorem: For any flow 𝑓 and any 𝑠-𝑡 cut (𝐴, 𝐵), 𝑣𝑓 ≤𝑐𝑎𝑝(𝐴,𝐵)
• Proof:
𝑣𝑓 =𝑓𝑜𝑢𝑡 𝐴 −𝑓𝑖𝑛 𝐴 ≤𝑓𝑜𝑢𝑡 𝐴
= σ𝑒 leaving 𝐴 𝑓(𝑒)
≤ σ𝑒 leaving 𝐴 𝑐(𝑒) = 𝑐𝑎𝑝(𝐴, 𝐵)
373F19 – Nisarg Shah 46
Cuts and Flows
• Theorem:Foranyflow𝑓andany𝑠-𝑡cut(𝐴,𝐵), 𝑣𝑓 ≤𝑐𝑎𝑝(𝐴,𝐵)
• Hence, max value of any flow ≤ min capacity of any 𝑠-𝑡 cut. • Wewillnowprove:
➢ Value of flow generated by Ford-Fulkerson = capacity of some cut
• Implications
➢ 1) Max flow = min cut
➢ 2) Ford-Fulkerson generates max flow.
373F19 – Nisarg Shah 47
Cuts and Flows
• Theorem: Ford-Fulkerson finds maximum flow.
• Proof:
➢ 𝑓 = flow returned by Ford-Fulkerson
➢ 𝐴∗ = nodes reachable from 𝑠 in 𝐺 𝑓
➢ 𝐵∗ = remaining nodes 𝑉 ∖ 𝐴∗
➢ Note: We look at the residual graph 𝐺 , but define the cut in 𝐺 𝑓
Graph 𝐺
𝐺 𝑓
373F19 – Nisarg Shah 48
Cuts and Flows
• Theorem: Ford-Fulkerson finds maximum flow.
• Proof:
➢ Claim: 𝐴∗, 𝐵∗ is a valid cut
o 𝑠 ∈ 𝐴∗ by definition
o 𝑡 ∈ 𝐵∗ because when Ford-Fulkerson terminates, there are no 𝑠-𝑡
paths in 𝐺 , so 𝑡 ∉ 𝐴∗ 𝑓
Graph 𝐺
𝐺 𝑓
373F19 – Nisarg Shah 49
Cuts and Flows
• Theorem: Ford-Fulkerson finds maximum flow.
• Proof:
➢ Blue edges = edges going out of 𝐴∗ ➢ Red edges = edges coming into 𝐴∗
Graph 𝐺
𝐺 𝑓
in 𝐺
in 𝐺
373F19 – Nisarg Shah 50
Cuts and Flows
• Theorem: Ford-Fulkerson finds maximum flow.
• Proof:
➢ Each blue edge 𝑢, 𝑣 must be saturated
o Otherwise 𝐺 would have its forward edge 𝑢, 𝑣 and then 𝑣 ∈ 𝐴∗ 𝑓
➢ Each red edge (𝑣, 𝑢) must have zero flow
o Otherwise 𝐺 would have its reverse edge (𝑢, 𝑣) and then 𝑣 ∈ 𝐴∗
𝑓
Graph 𝐺
𝐺 𝑓
373F19 – Nisarg Shah 51
Cuts and Flows
• Theorem: Ford-Fulkerson finds maximum flow.
• Proof:
➢ Each blue edge 𝑢, 𝑣 must be saturated ⇒ 𝑓𝑜𝑢𝑡 𝐴∗ ➢ Each red edge (𝑣,𝑢) must have zero flow ⇒ 𝑓𝑖𝑛 𝐴∗ ➢So𝑣 𝑓 =𝑓𝑜𝑢𝑡 𝐴∗ −𝑓𝑖𝑛(𝐴∗)=𝑐𝑎𝑝 𝐴∗,𝐵∗ ∎
= 𝑐𝑎𝑝(𝐴∗, 𝐵∗) = 0
Graph 𝐺
𝐺 𝑓
373F19 – Nisarg Shah 52
Max Flow – Min Cut
• Max Flow-Min Cut Theorem:
In any graph, the value of the maximum flow is equal to the capacity of the minimum cut.
• Our proof already gives an algorithm to find a min cut
➢ Run Ford-Fulkerson to find a max flow 𝑓
➢ Construct its residual graph 𝐺 𝑓
➢ Let 𝐴∗ = set of all nodes reachable from 𝑠 in 𝐺 𝑓
o Easy to compute using BFS
➢ Then (𝐴∗, 𝑉 ∖ 𝐴∗) is a min cut
373F19 – Nisarg Shah 53
Piazza Poll
Question
• There is a network 𝐺 with positive integer edge capacities.
• You run Ford-Fulkerson.
• It finds an augmenting path with bottleneck capacity 1, and after that iteration, it terminates with a final flow value of 1.
• Which of the following statement(s) must be correct about 𝐺?
(a) 𝐺 has a single 𝑠-𝑡 path.
(b) 𝐺 has an edge 𝑒 such that all 𝑠-𝑡 paths go through 𝑒. (c) The minimum cut capacity in 𝐺 is greater than 1.
(d) The minimum cut capacity in 𝐺 is less than 1.
373F19 – Nisarg Shah 54
Why Study Flow Networks?
• Unlike divide-and-conquer, greedy, or DP, this doesn’t seem like an algorithmic framework
➢ It seems more like a single problem
• Turns out that many problems can be reduced to this
versatile single problem
• Next lecture!
373F19 – Nisarg Shah 55