A 2.37332-Competitive Algorithm for Online Square Packing with Gravity

技术摘要：一种针对具有重力约束的在线正方形装箱问题的 2.37332-竞争算法

问题定义
本文研究了在具有 Tetris（俄罗斯方块）和重力约束 的轴平行正方形 在线条带装箱问题（online strip packing problem）。在该模型中，正方形按顺序到达，且在不知道未来物品信息的情况下，必须不可逆地放置在宽度为 1、高度无界的条带中。

• Tetris 约束： 进入的正方形必须遵循一条从上方到其最终位置的无碰撞、单调向下的路径。
• 重力约束： 正方形必须落在条带底部或先前放置的正方形的上表面上。
• 可行性： 一个几何为空的区域如果通过向下的路径不可达，或缺乏支撑，则可能无法使用。

目标是最小化总高度。性能通过 渐近竞争比 ($CR$) 来衡量，定义为 $\rho$ 的下确界，使得对于所有输入序列 $\sigma$，均满足 $A(\sigma) \le \rho \cdot OPT(\sigma) + \beta$，其中 $A(\sigma)$ 是算法高度，$OPT(\sigma)$ 是最优离线高度。

方法论：AsymmetricSlots（非对称槽位）
作者引入了 AsymmetricSlots，这是一种递归算法，改进了之前已知的最佳方法 SlotAlgorithm (Fekete et al., 2014)，后者使用的是二分（对称）层级结构。

1. 非对称层级：
   不同于将宽度为 $w$ 的槽位拆分为两个相等的半部分，该算法将其拆分为一个宽度为 $pw$的**宽子槽**和一个宽度为$qw$的**窄子槽**，其中$p \in (1/2, 1)$且$q = 1-p$。该层级结构在任何物品到达前即已固定。

2. 局部路由规则：
   当边长为 $a$ 的正方形到达时，它根据其相对于当前槽位宽度 $w$ 的大小进行层级下降：

   • 直接（Direct）： 如果 $a > pw$，则该正方形立即被分配到当前槽位。
   • 强制（Forced）： 如果 $qw < a \le pw$，则该正方形被强制进入宽子槽。
   • 灵活（Flexible）： 如果 $a \le qw$，则该正方形被路由到当前虚拟高度较小的子槽中（若高度相等，则优先选择宽子槽）。

3. 虚拟高度剖面与可行性：
   算法维护一个分段常数的虚拟高度剖面 $h(x)$ 来指导路由。分配到槽位 $T$ 的正方形通过其边长 $a$ 来更新该槽位的虚拟高度。

   • 引理 1 证明，尽管虚拟剖面可能会高估物理高度，但在 Tetris 和重力约束下，物理插入始终是可行的。具体而言，物理正方形总能落到一个支撑水平 $y^*$（由现有正方形或条带底部决定），且 $y^* \le$ 虚拟更新水平，从而确保下降过程中不会发生碰撞。

4. 通过局部计费进行分析：
   证明利用了**局部相位不变性（local phase invariant）**和计费论证，并利用了拆分的非对称性：

   • 强制正方形： 大正方形 ($a > qw$) 被强制进入特定路径。它们的面积足以“支付”它们所创造的高度 ($wa - \rho a^2 \le 0$)。
   • 灵活正方形： 小正方形 ($a \le qw$) 允许在子槽之间进行平衡。分析使用了一种“基于相位”的会计方法，算法维持一个信用额度 $\delta w^2$。非对称性确保了与灵活放置相关的损失在局部是受限的，并且不会随层级的深度而累积。
   • 相位闭合： 当放置了一个“直接”正方形（即对于子槽而言过大的正方形）时，一个槽位的相位结束，并重置虚拟剖面。

关键结果

1. 改进的正方形上界：
   通过优化拆分参数 $p$，作者得出了一个竞争比为 2.373318506... 的算法。

   • 最优参数 $p^\star$ 是 $(1/2, 1)$ 中方程 $16p^3 - 8p^2 + p - 1 = 0$ 的唯一根，得出 $p^\star \approx 0.5786$。
   • 得到的比率 $\rho^\star = 1/(1-p^\star) \approx 2.3733$。
   • 使用 $p = 11/19$ 的有理近似可得到一个简洁的比率 2.375 ($19/8$)。
   • 这改进了 Fekete 等人建立的此前最佳上界 $34/13 \approx 2.6154$。

2. 算法的下界：
   论文确定了 AsymmetricSlots 的一个特定下界。通过重复正方形构造，他们证明了对于包含 $p^\star$ 的 $p$ 范围，竞争比至少为 2。

   • 因此，$2 \le CR(AsymmetricSlots_{p^\star}) \le 2.3733...$
   • 该模型下任何确定性在线算法的一般下界仍为 $3/2$（来自 Fekete et al.）。

3. 向矩形的扩展：
   该框架被扩展到了具有有界长宽比 $\kappa$ 的矩形（其中宽度 $u$ 和高度 $v$ 满足 $u/\kappa \le v \le \kappa u$）。

   • 上界： 该算法实现了 $O(\kappa)$ 的渐近竞争比。
   • 下界： 通过交替使用细长垂直矩形和宽浅水平矩形的构造，证明了匹配的 $\Omega(\kappa)$ 下界。
   • 这确立了对长宽比的依赖关系最优为 $\Theta(\kappa)$。

意义与主张
论文声称提供了具有 Tetris 和重力约束的在线正方形装箱问题的已知最佳上界，将竞争比从 $\approx 2.6154$ 降低到了 $\approx 2.3733$。

• 方法论贡献： 从对称（二分）到非对称递归分解的转变，使得更高效的局部计费论证成为可能。非对称性将放置分为“强制型”（大）和“灵活型”（小）类别，防止了以往分析中存在的误差项累积问题。
• 范围： 这些结果是纯理论性的，侧重于确定性算法的竞争分析。论文并不声称解决了通用的离线问题，也不提供离线情况下的多项式时间近似方案（PTAS）。
• 局限性： 作者指出，算法特定的下界 (2) 与上界 (2.3733) 之间的差距仍然存在，正如一般下界 (1.5) 与上界之间的差距一样。论文建议未来的工作可以探索非自相似拆分或多于两个子槽位的拆分，以期缩小这些差距。

总之，这项工作精炼了具有物理约束的在线正方形装箱的理论极限，证明了非对称层级分解比以往已知的对称方法具有更优的竞争比。