CS计算机代考程序代写 database algorithm CS 577 - Network Flow

CS 577 – Network Flow

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Network Flow

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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.
1/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Network Flow

L R Ford Jr.

D. R. Fulkerson
1/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Flow Network

20 10

Basic Flow Network

Directed graph G = (V, E). Each edge e has ce ≥ 0.

Source s ∈ V and sink t ∈ V.
2/36
Internal node V/{s, t}.

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Flow Network

20 10

Basic Flow Network

Directed graph G = (V, E). Each edge e has ce ≥ 0.

Source s ∈ V and sink t ∈ V.
2/36
Internal node V/{s, t}.
Defining Flow
Flow starts at s and exits at t.

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Flow Network

20 10

Basic Flow Network

Directed graph G = (V, E). Each edge e has ce ≥ 0.

Source s ∈ V and sink t ∈ V.
2/36
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.

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Flow Network

20 10

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:

Capacity: For each e ∈ E, 0 ≤ f (e) ≤ ce.
2/36
i
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)

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Flow Network

20 10

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:

Capacity: For each e ∈ E, 0 ≤ f (e) ≤ ce.
i
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)

out in
2/36
Flow value v(f ) = f (s) = f (t)

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Maximum-Flow Problem

20 10

Max-Flow

Given a flow network G, what is the maximum flow value, i.e., what is the flow f that maximizes v(f )?
3/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Maximum-Flow Problem

20 10

Max-Flow

Given a flow network G, what is the maximum flow value, i.e., what is the flow f that maximizes v(f )?

v
Alternate View: Min-Cut
A Cut: Partition of V into sets (A, B) with s ∈ A and t ∈ B.
3/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Maximum-Flow Problem

20 10

Max-Flow

Given a flow network G, what is the maximum flow value, i.e., what is the flow f that maximizes v(f )?

v
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.
3/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Maximum-Flow Problem

20 10

Max-Flow

Given a flow network G, what is the maximum flow value, i.e., what is the flow f that maximizes v(f )?

v
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
3/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Maximum-Flow Problem

20 10

Max-Flow

Given a flow network G, what is the maximum flow value, i.e., what is the flow f that maximizes v(f )?

v
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.
3/36
Cut capacity: c(A, B) =
Σ
e out of A
c
e
Minimum-cut of G: The cut (A∗, B∗) that minimizes
c(A∗, B∗) for G.

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Maximum-Flow Problem

20 10

Max-Flow

Given a flow network G, what is the maximum flow value, i.e., what is the flow f that maximizes v(f )?

v
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.
3/36
Cut capacity: c(A, B) =
Σ
e out of A
c
e
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.

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Designing the Approach

TopHat 1

What is the max-flow value in the example?
4/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Designing the Approach

TopHat 2

What is the min-cut value in the example?
4/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Designing the Approach

30 t

u
20 10

20/20 10/0
s 30/20 t 10/0 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.
4/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Designing the Approach

30 t

u
20 10

20/20 10/0
s 30/20 t 10/0 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Residual Graph

u
20 10

s
v

20 10 t

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Residual Graph

u
20 10

s
v

20 10 t

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Augmenting Path

30 t

u
20 10

20 10

Augmenting Path
A simple directed path from s to t.
bottleneck(P, Gf ): Minimum residual capacity on augmenting path P.
7/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Augmenting Path

20 10 t

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Augmenting Path

30 t

u
20 10

20 10 t

v v
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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Augmenting Path

30 t

u
20 10

20 10 t

10 20 t

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Designing the Approach

30 t

u
20 10

20/20 10/0
s 30/20 t 10/0 20/20

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Designing the Approach

30 t

u
20 10

v
10

20 10

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 j) > v(f ), where v(f j) = v(f ) + bottleneck(P, Gf ) for an augmenting path P in Gf .
9/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 j) > v(f ), where v(f j) = 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 q more flow.

9/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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.

Theorem 2

Let C =
9/36
Σ
e out of s
e
c , the FF method terminates in at most C
iterations.

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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.

Theorem 2

Let C =
Σ
e out of s
e
c , the FF method terminates in at most C

iterations.
Proof.
TopHat 5: What technique?

9/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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.

Theorem 2

Let C =
Σ
e out of s
e
c , 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 j) > v(f ), where v(f j) = v(f ) + bottleneck(P, Gf ) for an augmenting path P in Gf .
Theorem 2

Let C =
9/36
Σ
e out of s
e
c , the FF method terminates in at most C
iterations.

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Analyzing the Algorithm

Observation 2

Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).

Runtime
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?
10/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Analyzing the Algorithm

Observation 2

Since G is connected,
m ≥ n/2. Hence,
O(m + n) = O(m).

Runtime
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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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.

10/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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:

10/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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:

1
Find an augmenting path: TH8: How can we do that?

10/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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:

1
Find an augmenting path: BFS or DFS: O(m + n) .

10/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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:

1
2
Find an augmenting path: BFS or DFS: O(m + n) . Update flow along path P: TH9: Time bound?

10/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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:

1
2
Find an augmenting path: BFS or DFS: O(m + n) . Update flow along path P: O(n).

10/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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:

1
2
3
Find an augmenting path: BFS or DFS: O(m + n) . Update flow along path P: O(n).
Build new Gf : TH10: Time bound?

10/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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:

Find an augmenting path: BFS or DFS: O(m + n) . Update flow along path P: O(n).
Build new Gf : O(m).
1
2
3
10/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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)

Find an augmenting path: BFS or DFS: O(m + n) . Update flow along path P: O(n).
Build new Gf : O(m).
1
2
3
10/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Choosing Good Augmenting Paths

100 100

100 100
v

Idea

Choose paths with large bottlenecks.
11/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Choosing Good Augmenting Paths

100 100

Idea

Choose paths with large bottlenecks.
Let Gf (∆) be a residual graph with edges of residual capacity
≥ ∆.
11/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Choosing Good Augmenting Paths

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.

i
11/36
. Σ
i i
Initialize ∆ := max 2 such that 2 ≤ max
e out of s e
(c ).
While ∆ ≥ 1:
While Gf (∆) contains an augmenting path P:
Update flow f by bottleneck(P, Gf (∆)) along P.
Set ∆ := ∆/2.

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Analyzing the Scaled Version

Scaled Version
Initialize f (e) = 0 for all edges.

i
. Σ
i i
Initialize ∆ := max 2 such that 2 ≤ max
e out of s e
(c ).
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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Analyzing the Scaled Version

Scaled Version
Initialize f (e) = 0 for all edges.

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Analyzing the Scaled Version

Scaled Version
Initialize f (e) = 0 for all edges.

i
. Σ
i i
Initialize ∆ := max 2 such that 2 ≤ max
e out of s e
(c ).

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.
12/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Analyzing the Scaled Version

Scaled Version
Initialize f (e) = 0 for all edges.

i
. Σ
i i
Initialize ∆ := max 2 such that 2 ≤ max
e out of s e
(c ).

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 + |lg C|.
12/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Analyzing the Scaled Version

Scaled Version
Initialize f (e) = 0 for all edges.

Runtime
Number of scaling phases: 1 + |lg C|.
Number of augmenting phases per scaling phases: .
12/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Analyzing the Scaled Version

Scaled Version
Initialize f (e) = 0 for all edges.

Runtime
Number of scaling phases: 1 + |lg C|.
Number of augmenting phases per scaling phases: O(m).
12/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Analyzing the Scaled Version

Scaled Version
Initialize f (e) = 0 for all edges.

Runtime
Number of scaling phases: 1 + |lg C|.
Number of augmenting phases per scaling phases: O(m). Cost per augmentation: TH13.
12/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Analyzing the Scaled Version

Scaled Version
Initialize f (e) = 0 for all edges.

Runtime
Number of scaling phases: 1 + |lg C|.
Number of augmenting phases per scaling phases: O(m). Cost per augmentation: O(m).
12/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Analyzing the Scaled Version

Scaled Version
Initialize f (e) = 0 for all edges.

Runtime
Number of scaling phases: 1 + |lg C|.
Number of augmenting phases per scaling phases: O(m). Cost per augmentation: O(m).
Overall: O(m2 log C).
12/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Analyzing the Scaled Version

Scaled Version
Initialize f (e) = 0 for all edges.

i
12/36
. Σ
i i
Initialize ∆ := max 2 such that 2 ≤ max
e out of s e
(c ).
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 + |lg C|.
Number of augmenting phases per scaling phases: O(m). Cost per augmentation: O(m).
Overall: O(m2 log C).
TopHat 14: Is this polynomial?

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Analyzing the Scaled Version

Scaled Version

Initialize f (e) = 0 for all edges.

i
. Σ
i i
Initialize ∆ := max 2 such that 2 ≤ max
e out of s e
(c ).
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 + |lg C|.
Number of augmenting phases per scaling phases: O(m). Cost per augmentation: O(m).
Overall: O(m2 log C).
TopHat 14: Is this polynomial? Yes, because |log C| is the # of bits needed to encode C.
12/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Strongly Polynomial

Definition
Polynomial in the dimensions of the problem, not in the size of the numerical data.
m and n for max-flow.
13/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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
13/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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

2 1

. , , Σ
Dinitz 1970: O min n 3 , m 2 m .

Preflow-Push 1974/1986: O(n3). Best: Orlin 2013: O(mn)
13/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Minimum Cut

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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.
14/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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).

14/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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
out in
= f (v) − f (v)
. Σ

14/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Max-Flow and Min-Cut

v∈A
Last line follows since Σv∈A\{s} .f out(v) − f in(v)Σ = 0.
Σ
v∈A
.
out in
Σ
f (v) − f (v) =
f (e)−
Σ Σ
e out of A e into A
out
f (e) = f (A
in
)−f (A) .

14/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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).
14/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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) .

v(f ) = f out(A) − f in(A) ≤ f out(A) =
14/36
Lemma 5
Let f be any s − t flow and (A, B) be any s − t cut. Then, v(f ) ≤ c(A, B).
Proof.
Σ
e out of A
f (e)
Σ
≤ ce = c(A, B)
e out of A

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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∗.

15/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Max-Flow equals Min-Cut

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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
path in Gf .
Let B∗ = V \
set of nodes for which ∃ an s − 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∗.
15/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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
path in Gf .
Let B∗ = V \
set of nodes for which ∃ an s − v A∗.

Consider e = (uj, vj): Claim f (e) = 0.
If not, then s − uj path in Gf which contradicts definition of
A∗ and B∗.
15/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Max-Flow equals Min-Cut

Consider e = (u, v): Claim f (e) = ce. Consider e = (uj, vj): Claim f (e) = 0. Therefore,
v(f ) = f out(A∗) − f in(A∗)
Σ
e
= c − 0
e out A∗
= c(A∗, B∗)

15/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Max-Flow equals Min-Cut

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Max-Flow equals Min-Cut

15/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 j) > v(f ). This implies that v(f j) > 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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. 16/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Bipartite Matching Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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). 17/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Bipartite Matching to Flow Network 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. Gj 18/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Bipartite Matching to Flow Network G Gj Theorem 10 |M∗| in G is equal to the max-flow of Gj, and the edges carrying the flow correspond to the edges in the maximum matching. 18/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Bipartite Matching to Flow Network Theorem 10 |M∗| in G is equal to the max-flow of Gj, 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. 18/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Bipartite Matching to Flow Network Theorem 10 |M∗| in G is equal to the max-flow of Gj, 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Bipartite Matching to Flow Network Gj G Runtime Assume n = |X| = |Y|, m = |E|. 18/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Bipartite Matching to Flow Network Gj G Runtime Assume n = |X| = |Y|, m = |E|. Overall: TH15. 18/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Bipartite Matching to Flow Network Gj G Runtime Assume n = |X| = |Y|, m = |E|. Overall: O(mn). 18/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Bipartite Matching to Flow Network Gj 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Edge-Disjoint Paths Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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. 19/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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: 19/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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. 19/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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: 19/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 Gj. 20/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 Gj. Runtime Basic FF method: O(mC) = O(mn). 20/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 Gj. 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? 20/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 Gj. 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 2 20/36 Find a simple path P from s to t: set flow to 0 along P; continue DFS from s. Find a path P with a cycle C before reaching t: set flow to 0 along C; continue DFS from start of cycle. Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball NBooudnedDsemand and Lower Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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).
21/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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

Capacity: For each e ∈ E, 0 ≤ f (e) ≤ ce.

ii
21/36
Conservation: For each v ∈ V, f in(v) − f out(v) = dv.

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Flow Network Extension

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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).

22/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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).

e e
For every edge e = (u, v), f out(u) = f in(v). Hence,
e
in out
e
f (v) − f (u) = 0.

22/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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).

e e
For every edge e = (u, v), f out(u) = f in(v). Hence,
in out
e e
f (v) − f (u) = 0.

Σv∈V dv = 0.

22/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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
22/36
D =
Σ
v:dv>0∈V
dv =
Σ
v:dv<0∈V −dv Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 = Σ dv = Σ −dv v:dv>0∈V v:dv<0∈V Not iff Feasibility =⇒ Σv∈V dv = 0, but Σv∈V dv = 0 =ƒ ⇒ feasibility. 22/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Reduction to Max-Flow Reduction from G (demands) to Gj (no demands) Super source s∗: Edges from s∗ to all v ∈ S with dV < 0 with capacity −dv. 23/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Reduction to Max-Flow Reduction from G (demands) to Gj (no demands) Super source s∗: Edges from s∗ to all v ∈ S with dV < 0 with capacity −dv. Super sink t∗: Edges from all v ∈ T with dV > 0 with capacity dv to t∗.
23/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Reduction to Max-Flow

Reduction from G (demands) to Gj (no demands)
Super source s∗: Edges from s∗ to all v ∈ S with dV < 0 with capacity −dv. Super sink t∗: Edges from all v ∈ T with dV > 0 with

v
23/36
v:d >0∈V
Σ Σ
v
v:d <0∈V v v d = −d in G j capacity dv to t∗. Maximum flow of D = shows feasibility. Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Another Flow Network Extension Adding Flow Lower Bound Adding Lower Bound For each edge e, define a lower bound Ae, where 0 ≤ Ae ≤ ce. 24/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Another Flow Network Extension Adding Flow Lower Bound Adding Lower Bound For each edge e, define a lower bound Ae, where 0 ≤ Ae ≤ ce. Flow Conditions Capacity: For each e ∈ E, Ae ≤ f (e) ≤ ce. i ii 24/36 Conservation: For each v ∈ V, f in(v) − f out(v) = dv. Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Another Flow Network Extension Adding Flow Lower Bound Adding Lower Bound For each edge e, define a lower bound Ae, where 0 ≤ Ae ≤ ce. Flow Conditions Capacity: For each e ∈ E, Ae ≤ f (e) ≤ ce. i 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Reduction to Only Demand Step 1: Reduction from G (demand + LB) to Gj (demand) Consider an f0 that sets all edge flows to Ae: v in out 0 0 L = f (v) − f (v) . if Lv = dv: Condition is satisfied. if Lv ƒ= dv: Imbalance. 25/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Reduction to Only Demand Step 1: Reduction from G (demand + LB) to Gj (demand) Consider an f0 that sets all edge flows to Ae: v in out 0 0 L = f (v) − f (v) . if Lv = dv: Condition is satisfied. For if Lv ƒ= dv: Imbalance. Gj: Each edge e, cej = ce − Ae and Ae = 0. Each node v, dvj = dv − Lv. 25/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Reduction to Only Demand Step 2: Reduction from Gj (demand) to Gjj (no demand) Super source s∗: Edges from s∗ to all v ∈ S with dV < 0 with capacity −dv. Super sink t∗: Edges from all v ∈ T with dV > 0 with

v
25/36
v:d >0∈V
Σ Σ
v
v:d <0∈V v v d = −d in G j capacity dv to t∗. Maximum flow of D = shows feasibility. Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Survey Design Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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. 26/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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. 26/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 cij products. 26/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 cij products. To be useful, each product must appear in at least pi and at most pji surveys. 26/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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? 26/36 Survey Rules Each customer receives a survey based on their purchases. Customer i will be asked about at least ci and at most cij products. To be useful, each product must appear in at least pi and at most pji surveys. Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Algorithm Design 27/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Algorithm Design 27/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Algorithm Design 27/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Algorithm Design Reduction Bipartite Graph: Customers to products with min of 0 and max of 1. Add s with edges to customer i with min of ci and max of cij. Add t with edges from product j with min pj and max of pjj. i 27/36 i Σ Σ j i i Edge (t, s) with min c and max c . All nodes have a demand of 0. Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Airline Scheduling Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Airline Scheduling Flights: (2 airplanes) Boston (6 am) – Washington DC (7 am) Philadelphia (7 am) – Pittsburgh (8 am) Washington DC (8 am) – Los Angeles (11 am) Philadelphia (11 am) – San Francisco (2 pm) San Francisco (2:15 pm) – Seattle (3:15 pm) Las Vegas (5 pm) – Seattle (6 pm) 1 2 3 4 5 6 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Airline Scheduling Flights: (2 airplanes) Boston (6 am) – Washington DC (7 am) Philadelphia (7 am) – Pittsburgh (8 am) Washington DC (8 am) – Los Angeles (11 am) Philadelphia (11 am) – San Francisco (2 pm) San Francisco (2:15 pm) – Seattle (3:15 pm) Las Vegas (5 pm) – Seattle (6 pm) 1 2 3 4 5 6 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; 28/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Airline Scheduling Flights: (2 airplanes) Boston (6 am) – Washington DC (7 am) Philadelphia (7 am) – Pittsburgh (8 am) Washington DC (8 am) – Los Angeles (11 am) Philadelphia (11 am) – San Francisco (2 pm) San Francisco (2:15 pm) – Seattle (3:15 pm) Las Vegas (5 pm) – Seattle (6 pm) 1 2 3 4 5 6 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. 28/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Airline Scheduling Flights: (2 airplanes) Boston (6 am) – Washington DC (7 am) Philadelphia (7 am) – Pittsburgh (8 am) Washington DC (8 am) – Los Angeles (11 am) Philadelphia (11 am) – San Francisco (2 pm) San Francisco (2:15 pm) – Seattle (3:15 pm) Las Vegas (5 pm) – Seattle (6 pm) 1 2 3 4 5 6 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Algorithm Design k = 2 planes Exercise: Reduce to a flow network Hint: Use lower bounds and demand. 29/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 t with 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Project Selection Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Project Selection 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Algorithm Design Reduction Use Min-Cut 31/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Algorithm Design Reduction Use Min-Cut Add s with edge to every project i with pi > 0 and capacity pi.
31/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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. 31/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball 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
31/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 = 31/36 Σ i i∈P:p >0
p
i
TH21: What is the capacity of the cut ({s}, P ∪ {t})?

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 31/36 ≤ C = Σ i i∈P:p >0
i
p which is
the capacity ({s}, P ∪ {t})

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 31/36 ≤ C = Σ i i∈P:p >0
i
p .
For edges of G, capacity is ∞ (or C + 1).

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Algorithm Analysis

Observation 4
If c(Aj, Bj) ≤ C, then A = Aj \ {s} satisfies precedence as edges of G have capacity > C.
32/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Algorithm Analysis

Observation 4
If c(Aj, Bj) ≤ C, then A = Aj \ {s} satisfies precedence as edges of G have capacity > C.
Lemma 12
Let (Aj, Bj) be a cut satisfies precedence; then
c(Aj, Bj) = C − Σi∈A pi.
32/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Algorithm Analysis

Observation 4
If c(Aj, Bj) ≤ C, then A = Aj \ {s} satisfies precedence as edges of G have capacity > C.
Lemma 12
Let (Aj, Bj) be a cut satisfies precedence; then
c(Aj, Bj) = C − Σi∈A pi.

Proof.
Consider the different edges:
(i, t): −pi for i ∈ A. (s, i): pi for i ∈/ A. c(Aj, Bj) = Σi∈A:pi<0 −pi + C − Σi∈A:pi>0 pi = C − Σi∈A pi

32/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Algorithm Analysis

Theorem 12
If (Aj, Bj) is a min-cut in Gj, then
A = Aj \ {s} is an optimal solution.
32/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Algorithm Analysis

Theorem 12
If (Aj, Bj) is a min-cut in Gj, then
A = Aj \ {s} is an optimal solution.

Proof.

j j
Obs: c(A , B ) = C −
Σ
i∈A
p
i

means feasible.
c(Aj, Bj) = C − profit(A)
⇐⇒ profit(A) = C − c(Aj, Bj)
Given that c(Aj, Bj) is a minimum, profit is maximized as C is a constant.

32/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Baseball Elimination

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Baseball Elimination
Wins

Games Left

New York 92

Toronto 91
Baltimore 91
Boston 90
33/36
NYY vs TOR TOR vs BAL BAL vs BOS BOS vs TOR NYY vs BAL

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Baseball Elimination
Wins

Games Left

New York 92

Toronto 91
Baltimore 91
Boston 90
33/36
NYY vs TOR TOR vs BAL BAL vs BOS BOS vs TOR NYY vs BAL
TH22: Is Boston Eliminated?

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Baseball Elimination
Wins

Games Left

New York 92

Toronto 91
Baltimore 91
Boston 90
33/36
NYY vs TOR TOR vs BAL BAL vs BOS BOS vs TOR NYY vs BAL
TH22: Is Boston Eliminated? Yes.

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Baseball Elimination

Games Left

Wins
New York 92

Toronto 91
Baltimore 91
Boston 90
NYY vs TOR TOR vs BAL BAL vs BOS BOS vs TOR NYY vs BAL

Why is Boston eliminated?
Case analysis:
Boston must win its 2 remaining games.
33/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Baseball Elimination

Games Left

Wins
New York 92

Toronto 91
Baltimore 91
Boston 90
NYY vs TOR TOR vs BAL BAL vs BOS 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.
33/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Baseball Elimination

Games Left

Wins
New York 92

Toronto 91
Baltimore 91
Boston 90
NYY vs TOR TOR vs BAL BAL vs BOS 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Baseball Elimination

Games Left

Wins
New York 92

Toronto 91
Baltimore 91
Boston 90
NYY vs TOR TOR vs BAL BAL vs BOS BOS vs TOR NYY vs BAL

Why is Boston eliminated?
Analytical approach:
Boston can finish with ≤ 92 wins.
33/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Baseball Elimination

Games Left

Wins
New York 92

Toronto 91
Baltimore 91
Boston 90
NYY vs TOR TOR vs BAL BAL vs BOS 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:
33/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Baseball Elimination

Games Left

Wins
New York 92

Toronto 91
Baltimore 91
Boston 90
NYY vs TOR TOR vs BAL BAL vs BOS 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.
33/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Baseball Elimination

Games Left

Wins
New York 92

Toronto 91
Baltimore 91
Boston 90
NYY vs TOR TOR vs BAL BAL vs BOS BOS vs TOR NYY vs BAL

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Algorithm Design

Let m be the max # of wins for z,
Sj = S \ {z}, and
g∗ = Σx,y∈Sj gxy.

Reduction
Nodes:
Source s, sink t. vx for each x ∈ Sj.
uxy for each pair x, y ∈ Sj.
35/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Algorithm Design

Let m be the max # of wins for z,
Sj = S \ {z}, and
g∗ = Σx,y∈Sj 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 FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Algorithm Design

Let m be the max # of wins for z,
Sj = S \ {z}, and
g∗ = Σx,y∈Sj gxy.

Solution
v(f ) = g∗: z is not eliminated.
35/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Algorithm Design

Let m be the max # of wins for z,
Sj = S \ {z}, and
g∗ = Σx,y∈Sj gxy.

Solution
v(f ) = g∗: z is not eliminated.
∗ in
Σ
x∈Sj
x
v(f ) = g = f (t) ≤ (m − w ) = m
j
Σ
x∈Sj
|S | − w
x
⇐⇒
xy
j
Σ Σ
x,y∈Sj x∈Sj
g ≤ m|S | − w
x
35/36

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Algorithm Design

Let m be the max # of wins for z,
Sj = S \ {z}, and
g∗ = Σx,y∈Sj gxy.

Solution
v(f ) = g∗: z is not eliminated.
x,y∈Sj
x∈Sj
35/36
∗ in
Σ
x∈Sj
x
v(f ) = g = f (t) ≤ (m − w ) = m
j
Σ
x∈Sj
|S | − w
x
⇐⇒ m|Sj| ≥ Σ gxy + Σ wx

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Algorithm Design

Let m be the max # of wins for z,
Sj = S \ {z}, and
g∗ = Σx,y∈Sj gxy.

Solution
v(f ) = g∗: z is not eliminated.
x,y∈Sj
x∈Sj
35/36
∗ in
Σ
x∈Sj
x
v(f ) = g = f (t) ≤ (m − w ) = m
j
Σ
x∈Sj
|S | − w
x
⇐⇒ m ≥ ( Σ gxy + Σ wx)/|Sj|

Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball

Algorithm Design

Let m be the max # of wins for z,
Sj = S \ {z}, and
g∗ = Σx,y∈Sj gxy.

Solution
v(f ) = g∗: z is not eliminated.
v(f ) < g∗: z is eliminated. 35/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Solution Characterization Let m be the max # of wins for z, Sj = S \ {z}, and g∗ = Σx,y∈Sj gxy. Theorem 13 Suppose z has been eliminated. Then, there is a set of items T ⊆ Sj such that: m|T| < Σx,y∈T gxy + Σx∈T wx 36/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Solution Characterization Let m be the max # of wins for z, Sj = S \ {z}, and g∗ = Σx,y∈Sj gxy. Theorem 13 Suppose z has been eliminated. Then, there is a set of items T ⊆ Sj such that: m|T| < Σx,y∈T gxy + Σx∈T wx Proof. Let (A, B) be a min-cut with c(A, B) = gj ≤ min{Σx,y∈Sj gxy, Σx∈Sj m − wx}. 36/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Solution Characterization Let m be the max # of wins for z, Sj = S \ {z}, and g∗ = Σx,y∈Sj gxy. Theorem 13 Suppose z has been eliminated. Then, there is a set of items T ⊆ Sj such that: m|T| < Σx,y∈T gxy + Σx∈T wx Proof. Let (A, B) be a min-cut with j c(A, B) = g ≤ min{ j g , Σ Σ x,y∈S x∈S j xy x m − w }. Consider a uxy ∈ A, x ∈ T, and y ∈/T (WLOG). Contradiction: c(uxy,y) = ∞. 36/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Solution Characterization Let m be the max # of wins for z, Sj = S \ {z}, and g∗ = Σx,y∈Sj gxy. Theorem 13 Suppose z has been eliminated. Then, there is a set of items T ⊆ Sj such that: m|T| < Σx,y∈T gxy + Σx∈T wx Proof. Let (A, B) be a min-cut with j c(A, B) = g ≤ min{ x,y∈S j xy g , Σ Σ x∈S j x m − w }. Consider a uxy ∈/A, and x, y ∈ T. Contradiction: c(A ∪ {uxy}, B \ {uxy}) = c(A, B) − gxy . 36/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Solution Characterization Let m be the max # of wins for z, Sj = S \ {z}, and g∗ = Σx,y∈Sj gxy. Theorem 13 Suppose z has been eliminated. Then, there is a set of items T ⊆ Sj such that: m|T| < Σx,y∈T gxy + Σx∈T wx Proof. Let (A, B) be a min-cut with c(A, B) = gj ≤ min{Σx,y∈Sj gxy, Σx∈Sj m − wx}. c(A, B) = gj = m|T| − Σx∈T wx + Σx,y∈/T gxy 36/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Solution Characterization Let m be the max # of wins for z, Sj = S \ {z}, and g∗ = Σx,y∈Sj gxy. Theorem 13 Suppose z has been eliminated. Then, there is a set of items T ⊆ Sj such that: m|T| < Σx,y∈T gxy + Σx∈T wx Proof. Let (A, B) be a min-cut with c(A, B) = gj ≤ min{Σx,y∈Sj gxy, Σx∈Sj m − wx}. c(A, B) = gj = m|T| − Σx∈T wx + g∗ − Σx,y∈T gxy 36/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Solution Characterization Let m be the max # of wins for z, Sj = S \ {z}, and g∗ = Σx,y∈Sj gxy. Theorem 13 Suppose z has been eliminated. Then, there is a set of items T ⊆ Sj such that: m|T| < Σx,y∈T gxy + Σx∈T wx Proof. Let (A, B) be a min-cut with c(A, B) = gj ≤ min{Σx,y∈Sj gxy, Σx∈Sj m − wx}. c(A, B) = gj = m|T| − Σx∈T wx + g∗ − Σx,y∈T gxy ⇐⇒ 0 > m|T| − Σx∈T wx − Σx,y∈T gxy as gj < g∗ 36/36 Network FlowMin-CutBipartiteEdge-DisjointExtensionsSurveysFlightsProjectsBaseball Solution Characterization Let m be the max # of wins for z, Sj = S \ {z}, and g∗ = Σx,y∈Sj gxy. Theorem 13 Suppose z has been eliminated. Then, there is a set of items T ⊆ Sj such that: m|T| < Σx,y∈T gxy + Σx∈T wx Proof. Let (A, B) be a min-cut with c(A, B) = gj ≤ min{Σx,y∈Sj gxy, Σx∈Sj m − wx}. Σ Σ c(A , B ) = g = m |T| − w + g − g j ∗ x xy x∈T x,y∈T Σ Σ ⇐⇒ m|T| < w + g x xy x∈T x,y∈T 36/36

Related Posts