复杂度理论作业6

5.1

每个点在 \([k]\)中随机取值，接下来证明这个期望是 \(\frac{k-1}{k}\)优秀的。

对于任何一条边 \((u,v)\),它对weight产生贡献的概率是\(\frac{k-1}{k}\),因此 \(E[W]=\sum\limits_{e \in E}w_{i,j}\frac{k-1}{k}\),显然 \(OPT \leq \sum w_{i,j}\),因而\(E[W]\geq \frac{k-1}{k}OPT\)

5.3

对于每个点，等概率的随机它进入\(U,W\),接下来说明这个算法是 \(\frac{1}{4}\)近似的。

对于任何一有向边，它对答案产生贡献的概率是\(\frac{1}{4}\),因而\(E[W]=\sum w_{i,j}\frac{1}{4}\geq \frac{OPT}{4}\)

5.6

a

\(x_i\)是1当且仅当\(i\in U\),\(z_{i,j}\)为1当且仅当这条边被选择。

b

边 \((i,j)\) 被选入贡献的概率是 \((\frac{x_i}{2}+\frac{1}{4})(\frac{3}{4}-\frac{x_j}{2})\)

由于\(\hat{x}\)是LP的解，因此 \(\frac{x_i}{2}+\frac{1}{4} \geq \frac{z_{i,j}}{2}+\frac{1}{4}\),\(\frac{3}{4}-\frac{x_j}{2}\geq \frac{1}{4}+\frac{z_{i,j}}{2}\)

故 \(E[W]=\sum w_{i,j} \cdot(\frac{z_{i,j}}{2}+\frac{1}{4})^2=\sum w_{i,j}(\frac{1}{16}+\frac{z^2_{i,j}}{4}+\frac{z_{i,j}}{4})\geq \sum w_{i,j}(\frac{z_{i,j}}{2}) \geq 2OPT\)