在线可移除正方形打包与目标日期分配问题解析

### 在线可移除正方形打包与目标日期分配问题解析 #### 在线可移除正方形打包算法（RSP）的竞争比分析 在正方形打包问题中，打包过程要么根据算法 RSP 的停止规则结束，要么由实例本身决定结束。由于在步骤 2 中不会移除任何正方形，此时的打包与最优打包相同，所以我们的分析主要聚焦于步骤 1 和步骤 3。若 RSP 在某一轮的步骤 1 停止，显然能达到竞争比。因此，为分析该算法，我们只需考虑步骤 3。 首先，我们要证明当 RSP 停止打包时，箱子内的打包面积至少为 1/3。然后，对于其他情况，证明竞争比至多为 3。以下有几个重要的引理用于算法分析： - **引理 3**：若算法 PB 无法打包正方形 Q，则 B 中所有未使用的砖块都小于 S(Q)，且对于每个 i = 1, 2, …，面积为 |S(Q)|/2^i 的未使用砖块至多有一个。 - **引理 4**：若 PB 算法无法打包 Q，则已使用砖块的总面积至少为 |B| - |S(Q)|。 - **引理 5**：给定砖块 A，任意两个总面积至多为 |A|/√2 的正方形可以一起打包到 A 中。 - **引理 6**：若 D1 ∪ D2 ∪ B 中存在一个小正方形，则 E1 ∪ E2 ∪ E3 中的打包面积大于 x^2，其中 x = 1 - 2√2/3。 - **引理 7**：在情况 (3.3) 中，D1 ∪ D2 ∪ B 中的打包面积大于 1/3 - 2^(-m)/18，情况 (3.3) 中移除的总面积至多为 1/18 + 2^(-m)/36。此外，若 m = 5，单位正方形内的打包面积大于 1/3。 - **引理 8**：若算法 RSP 停止打包，则单位正方形内的打包面积至少为 1/3。 - **引理 9**：若没有更多正方形到来，RSP 的竞争比至多为 3。 通过这些引理，我们可以得出定理 4：RSP 的竞争比为 3。 以下是引理 8 的证明过程，考虑了各种打包停止的情况： 1. **情况 (3.1)**：在打包 Q 之前，根据引理 4，D1 ∪ D2 ∪ B 中所有已打包砖块的面积至少为 2√2/3 - |S(Q)|。除了面积为 2^i|S(Q)| 的 t - 砖块外，所有已打包砖块的面积至少为 2√2/3 - |S(Q)| - 2^i|S(Q)|。所以，除了该 t - 砖块中的正方形 S 外，箱子内的打包面积至少为 1/3 - |S(Q)|/(2√2) - 2^i|S(Q)|/(2√2)，其中 i ≥ 2。由于在打包 Q 之前打包未停止，箱子内的打包面积小于 1/3，即 |S| < (|S(Q)| + 2^i|S(Q)|)/(2√2)。又因为 |Q| ≤ |S(Q)|/√2，所以 |S| + |Q| < 2^i|S(Q)|/√2 (i ≥ 2)。根据引理 5，S 和 Q 可以一起打包到面积为 2^i|S(Q)| 的 t - 砖块中。打包 Q 后，打包面积至少为 1/3。 2. **情况 (3.2)**：在打包 Q 之前，根据引理 4 和事实 4，打包面积至少为 (2√2/3 - |S(Q)|)/(2√2)。若 Q 可以打包到面积为 2|S(Q)| 的 t - 砖块中，则打包 Q 后，正方形箱子内的打包面积至少为 1/3。否则，根据引理 5，有 |P| + |Q| > 2|S(Q)|/√2，其中 P 是该 t - 砖块中的正方形。除了 P 和 Q，根据引理 4 和事实 4，箱子内的打包面积至少为 1/3 - |S(Q)|/(2√2) - 2|S(Q)|/(2√2)。若与 S(Q) 全等的任何 n - 砖块