Exercises 3

Ex 3.1 Greedy Algorithm for Knapsack Problem

记 \(V=\sum_{i=1}^{k}v_{i}, S=\sum_{i=1}^{k}s_{i}\), 最优解的 item value 之和为 \(\mathrm{OPT}\), 算法给出的 item value 之和为 \(V^{\ast} = \max \{ V, v_{i^{\ast}} \}\).

对于 \(\mathrm{OPT}\) 的上界，显然有 \(\mathrm{OPT} \leq V + (B-S) \frac{v_{k+1}}{s_{k+1}}\).

第一种情况，\(V^{\ast}=V\). 若 \(\mathrm{OPT} > 2V^{\ast}\), 于是 \((B-S) \frac{v_{k+1}}{s_{k+1}} > V\), 即 \(\frac{V}{B-S} < \frac{v_{k+1}}{s_{k+1}} < \frac{V}{S}\), 从而 \(\frac{v_{k+1}}{V} > \frac{s_{k+1}}{B-S} > 1\), 与 \(\frac{v_{1}}{s_{1}} \geq \frac{v_{2}}{s_{2}} \geq \cdots \geq \frac{v_{n}}{s_{n}}\) 矛盾，因此 \(\mathrm{OPT} / V^{\ast} \leq 2\).

第二种情况，\(V^{\ast} = v_{i^{\ast}}\), 显然此时 \(i^{\ast} > k+1 \implies \frac{v_{k+1}}{s_{k+1}} \geq \frac{v_{i^{\ast}}}{s_{i^{\ast}}}\) 以及 \(\frac{v_{i^{\ast}}}{s_{i^{\ast}}} < \frac{V}{S} \implies 1 < \frac{v_{i^{\ast}}}{V} < \frac{s_{i^{\ast}}}{S}\). 若 \(\mathrm{OPT} > 2V^{\ast} > V + v_{i^{\ast}}\), 于是 \((B-S) \frac{v_{k+1}}{s_{k+1}} > v_{i^{\ast}}\), 从而有 \(1 > \frac{B-S}{s_{k+1}} > \frac{v_{i^{\ast}}}{v_{k+1}}\), 与 \(v_{i^{\ast}} = \max_{i \in I}v_{i} \geq v_{k+1}\) 矛盾，因此 \(\mathrm{OPT} / V^{\ast} \leq 2\).

综上，\(V^{\ast} / \mathrm{OPT} \geq \frac{1}{2}\), 因此该算法是 \(1 / 2\)-approximation algorithm.

Ex 3.2 Improved FPAS for Knapsack Problem

前面学习的 FPAS 中，DP 状态方程第二维的上界为 \(\sum_{i=1}^{n}v_{i}'=O(n^{2} / \epsilon)\), 这个上界显然过于大了，如果 \(\mathrm{OPT}\) 存在上界 \(R\), 那么 \(R / \mu\) 必然也是 DP 最优解的上界，而根据 Ex 3.1 的结论，可以先跑一遍 Ex 3.1 中的贪心算法得到解 \(V^{\ast} \geq \frac{1}{2} \mathrm{OPT}\), 也就得到了更紧的 DP 上界 \(2V^{\ast} / \mu\), 此时修改枚举 DP 第二维的上界为 \(2V^{\ast} / \mu\) 即可得到更小的状态量，算法其余部分保持不变，于是 DP 的时间复杂度变为 \(O(n / \epsilon)\), 总的时间复杂度为 \(O(n^{2} / \epsilon + n\log n)\).

Ex 3.3 FPAS for Scheduling on a Single Machine

设 \(I^{\ast}\) 为最优解的 on-time job 集合，\(\mathrm{OPT}=\sum_{i \in I^{\ast}}w_{i}\).

对于任意最优解，将所有 on-time jobs 放在 late jobs 前面执行只会提前 on-time job 的完成时间和延后 late job 的完成时间，不会改变 \(I^{\ast}\)，因此 \(\mathrm{OPT}\) 不变依旧是最优解。

以此为前提，将所有 on-time job 按照 EDD 顺序执行，想象冒泡排序的过程，若 \(j\) 与 \(j+1\) 项的执行顺序交换，则说明 \(d_{j+1} < d_{j}\), 记交换前 \(j\) 的开始时间为 \(S_{j}\), 根据 job \(j+1\) 是 on-time job 有 \(S_{j}+p_{j}+p_{j+1} \leq d_{j+1} < d_{j}\), 交换后有 \(S_{j+1}=S_{j}\), 于是 \(j\) 的完成时间为 \(S_{j+1}+p_{j+1}+p_{j}=S_{j}+p_{j}+p_{j+1}<d_{j}\), 因此 \(j\) 依然是 on-time job, 从而将 on-time job 按照 EDD 顺序执行不改变 \(I^{\ast}\), 得证。

\(O(nW)\) DP 算法如下：

令 \(f(i, w)\) 表示当前考虑到第 \(i\) 个 job, total weight 为 \(w\) 时最早的完成时间（显然第一维可以滚掉）.

\[ \begin{array}{ll} 1 & \text{Set } f_{0,j} \leftarrow \infty \text{ for all } j > 0 \\ 2 & \text{Set } f_{0,0} \leftarrow 0 \\ 3 & \textbf{For } i \leftarrow 1 \textbf{ to } n \textbf{ do} \\ 4 & \quad \textbf{For } j \leftarrow W \textbf{ down to } w_i \textbf{ do} \\ 5 & \quad\quad f_{i,j} \leftarrow f_{i-1,j} \\ 6 & \quad\quad \textbf{If } f_{i-1,j-w_i} + p_i \leq d_i \textbf{ then} \\ 7 & \quad\quad\quad f_{i,j} \leftarrow \min(f_{i,j}, f_{i-1,j-w_i} + p_i) \\ 8 & \quad\quad \textbf{End} \\ 9 & \quad \textbf{End} \\ 10 & \textbf{End} \\ \end{array} \]

FPAS 如下：

令 \(w^{\ast} = \max_{i=1, \dots, n}w_{i}\), round \(w_{i}\) 到 \(\hat{w}_{i} = \left\lfloor \frac{w_{i}}{w^{\ast} / k} \right\rfloor\), 此时 \(\hat{W}=\sum_{i=1}^n \hat{w}_{i} \leq k \sum_{i=1}^n w_{i} / w^{\ast} \leq kn\). 然后 DP 可以得到最优解的 on-time job 集合 \(I\), 时间复杂度为 \(O(k n^{2})\).

此时有 \(\sum_{i \in I^{\ast}} \hat{w}_{i} \leq \sum_{i \in I} \hat{w}_{i}\), 且 \(\mathrm{OPT} = \sum_{i \in I^{\ast}} w_{i} \leq \frac{w^{\ast}}{k}\sum_{i \in I^{\ast}} \hat{w}_{i} + n \cdot \frac{w^{\ast}}{k}\), 于是

\[ \sum_{i \in I}w_{i} \geq \frac{w^{\ast}}{k} \sum_{i \in I} \hat{w}_{i} \geq \mathrm{OPT} - n \cdot \frac{w^{\ast}}{k} \geq \left( 1 - \frac{1}{k} \right)\mathrm{OPT} \]

令 \(\epsilon = \frac{1}{k}\), 于是 \(\sum_{i \in I}w_{i} / \mathrm{OPT} \geq 1 - \epsilon\), 因此该算法为 \((1-\epsilon)\)-approximation, 另外它的时间复杂度为 \(O(n^{2} / \epsilon)\), 因此是 FPAS.

Ex 3.4 Minimization Version of Scheduling on a Single Machine

\(O(n^{2})\) algorithm for the problem of minimizing the weight of the maximum-weight job that completes late:

先将 jobs 按照 weight 从小到大排序，记此时的 job 序列为 \(j_{1}, j_{2}, \dots, j_{n}\), 然后按照顺序枚举 job, 设当前枚举到的 job 为 \(j_{i}\), 令它为 maximum-weight job that completes late, 于是 \(j_{i+1}\) 到 \(j_{n}\) 都必须是 on-time job, 将这些 job 按照 EDD rule 排序检查这个序列是否满足所有约束，若能满足则 \(w_{j_{i}}\) 即是答案，否则继续枚举 \(j_{i}\).

FPAS for the problem of minimizing the total weight of the jobs that complete late:

先给出求解该问题的 DP 算法。

将 job 按照 EDD rule 排序，令 \(b_{j} = \sum_{i=1}^{j} p_{i} - d_{j}\) 表示若要将 job \(j\) 作为 on-time job 则前面的 late job 的 total processing time 至少要 \(\geq b_{j}\).

\[ \begin{array}{ll} 1 & \text{Initialize } F^0 = \{ (0,0) \}, G^0 \leftarrow \emptyset \\ 2 & \textbf{For } i = 1 \textbf{ to } n \textbf{ do} \\ 3 & \quad \text{Initialize } V^{(i)} \leftarrow \emptyset \\ 4 & \quad \textbf{For each } (W, C) \in F^{(i-1)} \textbf{ do} \\ 5 & \quad\quad \textbf{If } C + p_i \geq b_i \textbf{ then} \\ 6 & \quad\quad\quad \text{Add } (W + w_i, C + p_i) \text{ to } V^{(i)} \\ 7 & \quad\quad \textbf{End} \\ 8 & \quad \textbf{End} \\ 9 & \quad \text{Add elements from } F^{(i-1)} \text{ satisfying } C \geq b_i \text{ to } G^{(i)} \\ 10 & \quad \text{Set } F^{(i)} = G^{(i)} \cup V^{(i)} \\ 11 & \textbf{End} \\ \end{array} \]

由于 \(W\) 和 \(C\) 是同时增大的，因此任意 \(F^{(i)}\) 都有 \(\lvert F^{(i)} \rvert \leq \sum_{i=1}^{n}w_{i}\), 于是上述 DP 算法的时间复杂度为 \(O(n \lvert F^{(i)} \rvert)=O\left( n \sum_{i=1}^{n} w_{i} \right)\).

记 \(j^{\ast}\) 为 maximum-weight job that completes late, 显然 \(\mathrm{OPT} \geq w_{j^{\ast}}\).

将 \(w_{j}\) round 到 \(\hat{w}_{j}=\left\lfloor \frac{w_{j}}{w_{j^{\ast}} / k} \right\rfloor\) 后再进行 DP 并强制 \(w_{j} > w_{j^{\ast}}\) 的 job 为 on-time job, 由于 \(w_{j}\) 的大小变化不影响解的存在性且求解 \(w_{j^{\ast}}\) 时保证了该限制下必然有解，因此 DP 算法也必然有解。

记 DP 得到的解中 late job 的集合为 \(J\), 最优解的 late job 集合为 \(J^{\ast}\), 则 \(\sum_{j \in J} \hat{w}_{j} \leq \sum_{j \in J^{\ast}} \hat{w}_{j}\), 结合 \(\sum_{j \in J^{\ast}}w_{j} = \mathrm{OPT}\), 有

\[ \begin{aligned} \sum_{j \in J} w_{j} &\leq \frac{w_{j^{\ast}}}{k} \sum_{j \in J} \hat{w}_{j} + \lvert J \rvert \frac{w_{j^{\ast}}}{k} \\ &\leq \frac{w_{j^{\ast}}}{k} \sum_{j \in J^{\ast}}\hat{w}_{j} + n \frac{w_{j^{\ast}}}{k} \\ &\leq \mathrm{OPT} + \frac{n}{k} \cdot \mathrm{OPT} \\ &= \left( 1 + \frac{n}{k} \right)\mathrm{OPT} \end{aligned} \]

令 \(k = n / \epsilon\), 于是有 \(\sum_{j \in J}w_{j} \leq \left( 1 + \frac{1}{\epsilon} \right)\mathrm{OPT}\), 该算法 approximation 为 \(1 + 1 / \epsilon\).

令满足 \(w_{j} \leq w_{j^{\ast}}\) 的 job 集合为 \(J'\), 则只有 \(J'\) 中的 job 的 \(j'\) 会被考虑进 late job 中从而 \(\hat{w}_{j'}\) 可能在 DP 过程中被计入 \(W\), 于是该算法的时间复杂度为

\[ O\left( n \sum_{j \in J'}^{n} \hat{w}_{j} \right) = O\left( nk \sum_{j \in J'} \left\lfloor \frac{w_{j}}{w_{j^{\ast}}} \right\rfloor \right) = O(n^{3} / \epsilon) \]

综上，该算法是 \(\left( 1 + \frac{1}{\epsilon} \right)\)-approximate FPTAS.

Ex 3.5 Weighted Mean Finish Time

\(\textit{Proof.}\) 考虑任意最优解在任意一个 machine 上安排的 job 序列 \(j_{1}, j_{2}, \dots, j_{k}\), 由于可以通过交换相邻两项来达到排序的目的，因此考虑任意满足 \(\frac{p_{j_{i}}}{w_{j_{i}}} > \frac{p_{j_{i+1}}}{w_{j_{i+1}}}\) 的邻项 \(j_{i}\) 与 \(j_{i+1}\). 此时 \(C_{j_{i+1}}=C_{j_{i}}+p_{j_{i}}\), 记该 machine 上的 weighted completion time 为 \(W=\sum_{i=1}^{k}w_{j_{i}}C_{j_{i}}\).

交换 job \(j_{i}\) 与 \(j_{i+1}\), 则有 \(C_{j_{i}}' = C_{j_{i+1}}' + p_{j_{i+1}}=C_{j_{i}}+p_{j_{i+1}}\), 此时 \(W'-W=p_{j_{i+1}}w_{j_{i}} - p_{j_{i}}w_{j_{i+1}} < 0\), 即交换后的 schedule 更优，于是在任意 machine 上的 job 序列满足 \(\frac{p_{j}}{w_{j}}\) 为非递减的顺序最优，得证。

DP 算法如下：

先将所有 job 按照 \(\frac{p_{j}}{w_{j}}\) 从小到大排序，所有 machine 的状态可以用一个 \(m+1\) 维的 vector 表示，即 \(\vec{s} = (W, t_{1}, t_{2}, \dots, t_{m})\), 其中第 \(i+1 (1 \leq i \leq m)\) 维表示第 \(i\) 个 machine 目前的总处理时间，第 1 维表示当前的 weighted completion time.

\[ \begin{array}{ll} 1 & \text{Initialize } S^{(1)} \leftarrow \left\{ \left( p_{1}w_{1},\ p_{1},\ 0,\ \ldots,\ 0 \right) \right\} \\ 2 & \textbf{For } i = 2 \textbf{ to } n \textbf{ do} \\ 3 & \quad \text{Initialize } S^{(i)} \leftarrow \emptyset \\ 4 & \quad \textbf{For each } \left( W,\ t_{1},\ \ldots,\ t_{m} \right) \in S^{(i-1)} \textbf{ do} \\ 5 & \quad\quad \textbf{For } j = 1 \textbf{ to } m \textbf{ do} \\ 6 & \quad\quad\quad \text{Process job } i \text{ on machine } j: \\ 7 & \quad\quad\quad W' \leftarrow W + (t_{j} + p_{i})w_{i} \\ 8 & \quad\quad\quad t_{j}' \leftarrow t_{j} + p_{i} \\ 9 & \quad\quad\quad \text{Add } \left( W',\ t_{1},\ \ldots,\ t_{j}',\ \ldots,\ t_{m} \right) \text{ to } S^{(i)} \\ 10 & \quad\quad \textbf{End} \\ 11 & \quad \textbf{End} \\ 12 & \quad \textbf{For all } \left( W_{1},\ t_{1},\ \ldots,\ t_{m} \right),\ \left( W_{2},\ t_{1},\ \ldots,\ t_{m} \right) \in S^{(i)} \textbf{ with } W_{1} \leq W_{2} \textbf{ do} \\ 13 & \quad\quad S^{(i)} \leftarrow S^{(i)} \setminus \left\{ \left( W_{2},\ t_{1},\ \ldots,\ t_{m} \right) \right\} \\ 14 & \quad \textbf{End} \\ 15 & \textbf{End} \\ \end{array} \]

算法复杂度为 \(O\left( \min\left\{ m^n, n {{P+m-2}\choose{m-1}} \right\} \right)\), 其中 \(P=\sum_{j=1}^n p_{j}\).

Notes

• Ex 3.4 在书中引用的文献是 G. V. Gens and E. V. Levner. On approximation algorithms for universal scheduling problems [in Russian]. Izvestiya Akademii Nauk SSSR, Tehnicheskaya Kibernetika, 6:38–43, 1978. 但是网上找不到原文，借助 DeepSeek R1 联网搜索后参考了这篇论文：Fast approximation algorithm for job sequencing with deadlines