## 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 problem

### 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*|}$