《近似算法设计》第二章习题
2.3
首先有
\[OPT\geq \frac{1}{m} \sum w_i\]
同时对于最长的链 \(\ell\)
\[OPT\geq \sum_{i\in \ell}w_i\]
考虑在 \([a_i,b_i]\) 时段每一个 processor 都在工作。
则
\[|\cup [a_i,b_i]|\leq \frac{1}{m}\sum w_i\leq OPT\]
同时对于 \((b_{i+1},a_{i+2})\) 里面的每一个工作，他一定有 \((b_i,a_{i+1})\) 里的前序，否则他就可以在 \((b_{i},a_{i+1})\) 里处理。
所以这些位置的长度之和不超过最长链，不超过 \(OPT\)
所以是 2-approximation.
2.5
取欧拉序，依次连边
2.10
考虑第一次最优选择是 \(e_1\) ，第二次最优选择是 \(e_2\)。
\[f(S+e_1+e_2)+f(S)\leq f(S+e_1)+f(S+e_2)\]
整理得
\[f(S+e_1+e_2)-f(S+e_1)\leq f(S+e_2)-f(S)\leq f(S+e_1)-f(S)\]
所以 \(f\) 的选择是“凸”的。
所以他满足 2.6 中的条件
\[f(S+e)-f(S)\geq \frac{1}{k}(f(O)-f(S))\]
所以就得到了 \((1-1/e)\)-approximation
2.11
和 2.10 类似
假设存在一个 \((1-1/e+\epsilon)\)-approximation，我们给出一个 Set Cover 的 \(O(n^{O(\log\log n)})\) 的做法。
显然 Set Cover 可以很快转化成 Coverage Problem
我们可以从 \(1\) 到 \(m\) 调用这个算法，设第一次得到一个大于 \((1-1/e+\epsilon)m\) 的返回值时，记录 \(k_0\)，显然 \(OPT\geq k_0\)。
然后把覆盖的这些位置全部都扔掉，然后再调用，再扔掉，最多调用
\[\ell\leq \log_{1/(1-\frac{1}{e}+\epsilon)}n<\ln n\]
次，最后得到的近似解 \(\leq \ell k_0\leq c\ln n\cdot OPT(c<1)\)。
2.16
CF600F