# 算法设计与分析笔记0x0B —— 网络流应用(2)

Table of Contents

## Image Segmentation 图像分割

• $a_i$, likelihood pixel i in foreground.
• $b_i$, likelihood pixel i in background.
• $p_{ij}$, separating penalty for labeling one of i and j as foreground

Goal:

• Accuracy: if $a_i > b_j$ in isolation, prefer to label i in foreground.
• Smoothness: if many neighbors of i are labeled foreground, we should be inclined to label i as foreground.
• Maximize: $\sum_{i\in A}a_i + \sum_{j\in B}b_j -\sum_{(i,j)\in E}p_{ij}$

• 最小化 vs. 最大化
• 转换为最小化: $(\sum_{i\in V}a_i – \sum_{j\in V}b_j)-\sum_{i\in A}a_i – \sum_{j\in B}b_j +\sum_{(i,j)\in E}p_{ij}$
• 无源点汇点
• 无向图
• 原来的图: 网格状无向边
• 将每条无向边转换为两条有向边
• Add source to correspond to foreground; add sink to correspond to background

Consider min cut(A,B) in G’.

$$cap(A,B)=\sum_{j\in B}a_j+\sum_{i\in A}b_i+\sum_{(i,j)\in E}p_{ij},i\in A, j\in B$$

## Project Selection

• Set P of possible projects. Project v has associated revenue $p_v$.
• Set of prerequisites E. If (v,w) ∈ E, can’t do project v unless also do project w. (无先后顺序要求, 要求同时做)
• A subset of projects A ⊆ P is feasible if the prerequisite of every project in A also belongs to A.
• Goal: Choose a feasible subset of projects to maximize revenue.

Prerequisite Graph

### Min Cut Formulation

• All prerequisite edges have capacities ∞.
• Add source point pointing to all projects that have positive revenues.
• Add sink point pointed by all projects that have negative revenues.
• (A,B) is min cut iff A-{s} is optimal set of projects.
• 若存在依赖关系，(A,B)的cut就是∞.

(A, B) is min cut iff A – { s } is optimal set of projects.

• Infinite capacity edges ensure A – { s } is feasible.
• Max revenue because:

• 化简后: cap(A,B)(最小) = 所有节点盈利之和 – A集合里总revenue(最大)

Open Pit Mining

• Blocks of earth are extracted from surface to retrieve ore.
• $p_v$ = value of ore – processing cost
• Ores have dependency relation(DAG).
• Goal: 最大化盈利

## Baseball Elimination

• 对于一个队伍i, 赢得场次$w_i$, 输的场次$l_i$, 待比赛场次$r_i$, 和队伍j的待比赛场次$r_{ij}$.
• Set of teams S, z ∈ S.
• 队伍z有可能赢得冠军吗?(可并列)
• Source points to all game noes(i-j) with weight $r_{ij}$.
• A game node(i-j) points to team nodes i and j with weight ∞.
• Each team node i points to sink with weight $w_z + r_z – w_i$.(how many games team i can win then it won’t exceed team z.)

Theorem: Team z is not eliminated iff max flow saturates all edges leaving source.

• Integrality theorem => each remaining game between x and y added to number of wins for team x or team y.
• Capacity on (x, t) edges ensure no team wins too many games.

Certificate of elimination. R is set of teams

• Have w(R) = 278.
• r(R) = 27
• Average win: (278+27)/4 > 76.

### Certificate of Elimination

$$T\subseteq S, w(T):=\sum_{i\in T}w_i,g(T):=\sum_{{x,y}\subseteq T}g_{xy}$$
w(T) is the number of wins
g(T) is the number of remaining games.

Theorem Team z is eliminated iff there exists a subset T* such that
$$\frac{w(T*)+g(T*)}{|T*|}>w_z + g_z$$

Proof. <=

• The average number of wins of teams in T* is larger than the maximum number of wins of z

Proof. =>

• Use max flow formulation, and consider min cut (A, B).
• Define T* = team nodes on source side of min cut.
• Observe x-y ∈ A iff both x ∈ T* and y ∈ T*.
• infinite capacity edges ensure if x-y ∈ A then x ∈ A and y ∈ A
• if x ∈ A and y ∈ A but x-y ∈ B, then adding x-y to A decreases capacity of cut

• Since z is eliminated, by max-flow min-cut theorem:

• Rearranging terms: $w_z + g_z < \frac{w(T*)+g(T*)}{|T*|}$