CS170 Efficient Algorithms and Intractable Problems Section7

课程主页：

https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

课程视频：

https://www.bilibili.com/video/BV1wK411g7ck

这次回顾Section 7。

1. Job Assignment

(a)

优化的变量是第$i$个人在第$j$个工作上分配的时间$x_{ij}$。

(b)

约束：

$$\begin{aligned} \sum_{i=1}^I x_{ij} &\le 1 , j=1,\ldots, J, 第j份工作分配的总时间小于等于1\\ \sum_{j=1}^{J} x_{ij} &\le 1,i=1,\ldots, I,第i个人的总工作时间小于等于1\\ x_{ij}&\ge 0, i=1,\ldots, I,j=1,\ldots, J \end{aligned}$$

(c)

优化目标为

$$\sum_{ij}a_{ij}x_{ij}$$

2. Understanding convex polytopes

(a)

任取$x,y \in \Omega$，那么

$$\begin{aligned} Ax &\le b\\ Ay &\le b \end{aligned}$$

$\forall \lambda\in [0,1]$，我们有

$$\begin{aligned} \lambda Ax &\le\lambda b\\ (1-\lambda)Ay &\le(1-\lambda) b\\ \lambda Ax + (1-\lambda)Ay &\le b \end{aligned}$$

因此

$$\lambda Ax + (1-\lambda)Ay \in \Omega$$

即$\Omega$是凸集。

(b)

$$\begin{aligned} g(\lambda)&=f(\lambda y+(1-\lambda) z)\\ &= c^T (\lambda y+(1-\lambda) z)\\ &= \lambda c^T y +(1-\lambda) c^Tz \end{aligned}$$

注意$g(\lambda)$关于$\lambda$是线性函数，并且$\lambda\in [0,1]$，所以最大值在$\lambda = 0$或$\lambda =1$处取到。

(c)

如果全局最大值$x$不是顶点，那么$x$在端点是$y,z$的线段上，根据(b)可得

$$f(x)\le \min(f(y),f(z))$$

3. Residual in graphs

(a)

略。

(b)

最大流为$11$，分别为：

• $4:S\to A\to C\to T$
• $3: S\to A\to B\to T$
• $4:S\to B\to T$

最小割为：

• $\{S,A,B\}, \{C,T\}$

4. Verifying a max-flow

只要验证删除最大流后的剩余网络$G^f$不存在$S$至$T$的路径即可，利用DFS即可解决，时间复杂度为$O(|V|+|E|)$。