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

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

Leave a Reply

Your email address will not be published.