算法导论35.4 Exercises 答案
35.4-1
如果第\(i\)个子句同时包含了一个变量及其否定形式，那么这个子句的值恒为\(1\)，因此\(\Pr\{\text{clause }i\text{ is not satisûed}\}=1\)；否则有\(\Pr\{\text{clause }i\text{ is not satisûed}\}=7/8\).
因此计算随机变量\(\displaystyle{Y=\sum_{i=1}^m Y_i}\)的期望，有
\(\begin{aligned} E[Y]&=E\left[\sum_{i=1}^m Y_i\right]\\ &=\sum_{i=1}^m E[Y_i]\\ &\ge 7m/8 \end{aligned}\)
这意味着这个算法的近似比例的上界为\(m/(7m/8)=8/7\)，因此原结论成立。
35.4-2
这个算法和定理35.6时的一样，即以\(1/2\)的概率将每个变量设置成\(1\)，以\(1/2\)的概率将每个变量设置成\(0\)。
证明过程和定理35.6的类似，令示性随机变量\(Y_i\)表示第\(i\)个子句被满足。考虑如下行为：
- 如果第\(i\)个子句同时包含了一个变量及其否定形式，那么其必定是满足的，因此有\(E[Y_i]=1\)。
- 否则，如果第\(i\)个子句包含了\(k\)个变量对应的文字，那么可见子句\(Y_i\)中所有文字的设置都是相互独立的。只有这\(k\)个文字的值都被设置成\(0\)时，才会导致第\(k\)个不满足。因此，\(E[Y_i]=1-1/2^k\)。
需要注意的是，无论哪种情况，都有\(E[Y_i]\ge 1/2\)。计算随机变量\(\displaystyle{Y=\sum_{i=1}^m Y_i}\)的期望，有
\(\begin{aligned} E[Y]&=E\left[\sum_{i=1}^m Y_i\right]\\ &=\sum_{i=1}^m E[Y_i]\\ &\ge m/2 \end{aligned}\)
这意味着这个算法的近似比例的上界为\(m/(m/2)=m\)，因此原结论成立。
35.4-3
对于图\(G=(V,E)\)中的每条边\(e\in E\)，定义示性随机变量\(X_e\)表示\(e\)中的两个顶点处在不同的集合中。
由于\(e=(u,v)\)都是随机将两个顶点以\(1/2\)概率独立地分配到集合\(S\)或者是\(V-S\)中，因此有\(\Pr\{e\text{ belongs to a cut}\}=\Pr\{u\in S\land v\in V-S\}+\Pr\{v\in S\land u\in V-S\}=1/2\)。因此有\(E[X_e]=1/2\)。
定义示性随机变量\(X\)表示这个割的权值\(\displaystyle{X=\sum_{e\in E} X_e}\)的期望值\(E[X]\)，那么有
\(\begin{aligned} E[X]&=E\left[\sum_{e\in E} X_e\right]\\ &=\sum_{e\in E} E[X_e]\\ &=|E|/2 \end{aligned}\)
对于图\(G=(V,E)\)，它最佳的一个割\((S,V-S)\)也就只能取出\(E\)中的所有边。最终这个算法的近似比例的上界为\(|E|/(|E|/2)=2\)，因此原结论成立。
35.4-4
证明的思路是：对于一组可行解\(\overline{x}\)，其中某些节点\(v\)满足\(\overline{x}(v)>1\)，那么我们可以构造一组新可行解\(\overline{x'}\)，使得\(\displaystyle{\sum_{v\in V}\overline{x}(v)w(v)>\sum_{v\in V}\overline{x'}(v)w(v)}\)。
接下来构造可行解\(\overline{x'}\)：
\(\overline{x'}(v)= \left \{\begin{aligned} &x(v) & & \text{if}\quad x(v)\le 1 \\ &1 & & \text{if}\quad x(v)>1 \\ \end{aligned}\right.\)
由于我们需要最小化\(\displaystyle{\sum_{v\in V}x(v)w(v)}\)的值，通过比较这两个可行解的优劣性，有：
\(\begin{aligned} \sum_{v\in V}\overline{x'}(v)w(v)-\sum_{v\in V}\overline{x}(v)w(v)&=\sum_{v\in V,x(v)>1}(\overline{x'}(v)-\overline{x}(v))w(v)\\ &<0 \end{aligned}\)
因此\(\overline{x'}\)比\(\overline{x}\)更优。
接下来证明其它约束仍然成立。首先证明不等式35.18，可行解\(\overline{x'}\)只是将\(\overline{x}\)中超过\(1\)的可行解修改成\(1\)，因此不等式35.18仍然成立。接下里证明不等式35.16。由于\(\overline{x'}\)仍然是非负数，因此\(\forall v\in V\)，如果\(x(v)>1\)，有\(\overline{x}(v)=1\)，那么对于\(\forall(u,v)\in E\)，仍然有\(\overline{x'}(u)+\overline{x}(v)\ge 1\)，不等式35.16仍然成立。
因此，构造出的\(\overline{x'}\)是一个满足不等式35.17的可行解，因此不等式35.17是多余的。