复杂度理论作业5

4.2

对于某对 \(i,i+1\) 他们的贡献为 \(w_i \cdot(C_{i-1}+p_i)+w_{i+1} \cdot(C_{i-1}+p_i+p_{i+1})\)

考虑交换它们，则贡献变为 \(w_{i+1}\cdot (C_{i-1}+p_{i+1})+w_{i}\cdot (C_{i-1}+p_{i}+p_{i+1})\) 由于是最优解，因此交换不会使得答案更优，因此 \[w_i \cdot(C_{i-1}+p_i)+w_{i+1} \cdot(C_{i-1}+p_i+p_{i+1})\leq w_{i+1}\cdot (C_{i-1}+p_{i+1})+w_{i}\cdot (C_{i-1}+p_{i}+p_{i+1})\]

化简得 \(\frac{w_i}{p_i} \geq \frac{w_{i+1}}{p_{i+1}}\)

4.3

构造LP：

min：\(\sum\limits_{j \in [n]}w_j C_j\)

subject to: \(C_j-p_j \geq C_i\) \(\forall i \prec j\)

\(\sum\limits_{j \in S}p_jC_j \geq \frac{1}{2}p^2(S)\) \(\forall S \subseteq N\)

将求出的解从小到大重新排列为\(C^*_{j}\),显然该LP的最优解是小于等于OPT的。

按照LP给出的解的大小顺序，按次序完成任务，接下来证明 \(C^N_j \leq 2C^*_j\):

对于第二组LP的限制条件，取 \(S=[j]\),容易得到 \(C_j\cdot p([j]) \geq \sum\limits_{i \in [j]}C_i\cdot p_i \geq \frac{1}{2}p([j])\cdot C_j\) 故\(p([j]) \leq 2C^*_j\)

同时，\(C^N_j \leq p([j])\)故得证。