《近似算法设计》第三章习题

3.1

对于一个最优解 \(O\)，我们把他分成两部分，第一部分是按照 \(v_k/s_k\) 从大到小排序之后选出来的一个前缀，记这部分的价值为 \(\nu_1\)，大小记为 \(\sigma_1\)，剩下的部分是第二部分，代价记为 \(\nu_2\)，大小记为 \(\sigma_2\)

若 \(\nu_1\) 大于 \(\nu_2\)，则按照第一种选法选出来的价值 \(\geq \nu_1\geq (1/2)OPT\)

若 \(\nu_1\) 小于 \(\nu_2\)，设第一部分的下一个为 \(k\)，则 \(s_k>\sigma_2\)，因为 \(v_k/s_k\geq \nu_2/\sigma_2\)，\(v_k\geq \nu_2\geq (1/2)OPT\)

3.2

设 3.1 得到的结果为 \(M\)，将所有的 \(v_i\) 变为 \(\lfloor nv_i/\epsilon M\rfloor\)，则

\[\sum_{k\in O}v^\prime _k\leq \frac{n}{\epsilon M}\sum_{k\in O} v_k=\frac{2n}{\epsilon}\]

因此可以将 dp 的上限设为 \(n/\epsilon\)，最终复杂度为 \(O(n^2/\epsilon)\)

3.3

\(O(nW)\) 的做法就是一个很显然的 dp，维护最小值即可。

考虑我们要求一个 \((1-\epsilon)\) 近似，设 \(\mu=\epsilon W/n\)，设 \(w_i^\prime=\lfloor w_i/\mu\rfloor\)，对于 \(w^\prime_i\) 做上面的 dp，设我们得到的对应选出的集合为 \(S\)，真实最优解为 \(O\)

\[ \begin{aligned} \sum_{i\in S}w_i&\geq \mu\sum_{i\in S}w^\prime_i \\ &\geq \mu \sum_{i\in O}w^\prime_i \\ &\geq \sum_{i\in O}w_i-\mu|O| \\ &\geq OPT-\mu n \\ &\geq OPT-\epsilon W \\ &\geq (1-\epsilon)OPT \end{aligned} \]

即解决。

3.4

不会。

原论文是俄语的看不懂（

3.5

dp 还是好搞的，用 \(f(i,t_1,t_2,\cdots,t_m)(t_1\geq t_2\geq \cdots \geq t_m)\) 表示前 \(i\) 个任务安排好了，各个处理器用时是多少 最后的代价最小是多少。

下面考虑怎么确定 \(OPT_m\) 的范围，一个比较显然的界是 \(OPT_m\geq \dfrac{1}{m}OPT_1\)，其中 \(OPT_1\) 表示只有一个处理器的最优值，这个可以直接 \(O(n)\) 算出来。（实际上似乎有更优的界 \(OPT_m\geq \dfrac{n+m}{(n+1)m}OPT_1\)，但是 \(1/m\) 已经足够）

为了实现近似算法，我们需要换一种 dp 的形式，感觉在 OI 里也见到过。

设 \(G(i,T)\) 表示满足 \(f(i,t_1,\cdots,t_m)=T\) 的 \((t_1,\cdots,t_m)\) 的集合。

一个引理是对于相同的 \(T\) ，最多只有 \(n^{m-2}\) (感觉可以 generalize，但是似乎 \(m>2\) 会有一些 casework)个不同的 \((t_1,\cdots,t_m)\) 是有用的，其他的一些是显然不优的。（如对于 \(m=2\) 我们只需要保留一个）

设 \(\mu=\dfrac{\epsilon}{nm}OPT_1\)，对于 \(G(i,T)\) 的每一个 \(T\)，我们用 \(\lfloor T/\mu \rfloor\) 来替代他，维护 \(G(i,T^\prime)\) 中的 \(n^{m-2}\) 个元素一一进行转移。

这样的话，每一步 \(T\) 上的误差不超过 \(\mu\)，最终的总误差不超过 \(\dfrac{\epsilon OPT_1}{m}\leq \epsilon OPT_m\)。

复杂度为 \(O(n^m/\epsilon)\)，实现了 FTAS。