A 2.37332-Competitive Algorithm for Online Square Packing with Gravity

技術要約：重力を伴うオンライン正方形パッキングにおける 2.37332-競争的アルゴリズム

問題定義
本論文は、テトリスおよび重力の制約下における、軸に平行な正方形のオンライン・ストリップパッキング問題を扱う。このモデルでは、正方形は将来のアイテムに関する知識がない状態で逐次的に到着し、高さが無制限の幅1のストリップ内に、一度配置すると変更できない形で配置されなければならない。

• テトリス制約： 到着した正方形は、上方から最終位置まで、衝突のない単調な下降経路を辿る必要がある。
• 重力制約： 正方形は、ストリップの底または既に配置された正方形の上面に静止しなければならない。
• 実現可能性： 幾何学的に空の領域であっても、下方への経路が到達不能である場合や、支持（サポート）が欠けている場合は、使用不能となる可能性がある。

目的は、パッキングの総高さを最小化することである。性能は、すべての入力シーケンス $\sigma$ に対して $A(\sigma) \le \rho \cdot OPT(\sigma) + \beta$ を満たす $\rho$ の下限値（infimum）として定義される漸近的競争比（$CR$）によって測定される。ここで、$A(\sigma)$ はアルゴリズムの高さ、$OPT(\sigma)$ は最適なオフラインの高さである。

手法：AsymmetricSlots
著者は、二分（対称的）な階層構造を用いた従来の最良手法である SlotAlgorithm (Fekete et al., 2014) を改良した、再帰的アルゴリズムである AsymmetricSlots を導入する。

1. 非対称階層：
   幅 $w$ のスロットを2つの等しい半分に分割するのではなく、幅 $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 は、仮想プロファイルが物理的な高さを過大評価する可能性があるにもかかわらず、テトリスおよび重力の制約下で物理的な挿入が常に実現可能であることを証明している。具体的には、物理的な正方形は、仮想更新レベル以下の支持レベル $y^*$（既存の正方形またはストリップの底によって決定される）まで常に落下可能であり、これにより下降中の衝突が発生しないことが保証される。

4. 局所的なチャージングによる分析：
   証明は、局所的なフェーズ不変量と、分割の非対称性を利用したチャージング（課金）議論を用いる：

   • Forced Squares（強制された正方形）： 大きな正方形 ($a > qw$) は特定の経路に強制される。それらの面積は、それらが生成する高さに対して十分な支払い能力を持つ ($wa - \rho a^2 \le 0$)。
   • Flexible Squares（柔軟な正方形）： 小さな正方形 ($a \le qw$) は、チャイルド間でのバランス調整を可能にする。分析では、「フェーズベース」の会計を用い、アルゴリズムはクレジット $\delta w^2$ を保持する。この非対称性により、柔軟な配置に伴う損失は局所的に限定され、階層の深さとともに蓄積しないことが保証される。
   • フェーズの終了（Phase Closure）： スロットにおけるフェーズは、「ダイレクト」な正方形（子には大きすぎる正方形）が配置されたときに終了し、仮想プロファイルをリセットする。

主要な結果

1. 正方形に対する改善された上界：
   分割パラメータ $p$ を最適化することにより、著者は 2.373318506... の競争比を導出する。

   • 最適なパラメータ $p^\star$ は、$16p^3 - 8p^2 + p - 1 = 0$ の $(1/2, 1)$ における唯一の根であり、$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$ が $p^\star$ を含む範囲において、競争比が少なくとも 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)$ であることが確立される。

意義と主張
本論文は、テトリスおよび重力の制約下におけるオンライン正方形パッキング問題に対して、最良の既知の上界を提供すると主張しており、競争比を $\approx 2.6154$ から $\approx 2.3733$ へと減少させている。

• 方法論的貢献： 対称的（二分的）な分解から非対称な再帰的分解への転換により、より効率的な局所チャージング議論が可能となった。非対称性は、配置を「強制された（大きい）」ものと「柔軟な（小さい）」ものに分離し、従来の分析を困難にしていた誤差項の蓄積を防いでいる。
• 範囲： 結果は厳密に理論的なものであり、決定論的アルゴリズムの競争分析に焦点を当てている。本論文は、一般的なオフライン問題を解決したり、オフラインの場合の多項式時間近似スキームを提供したりすることを目的としていない。
• 限界： 著者は、アルゴリズム固有の下界（2）と上界（2.3733）の間の差、および一般的な下界（1.5）と上界の間の差が依然として残っていることを指摘している。論文は、将来の研究において、非自己相似的な分割や、2つより多いサブスロットの探索が、これらのギャップを埋める可能性があることを示唆している。

要約すると、本研究は物理的制約下におけるオンライン正方形パッキングの理論的限界を洗練させ、非対称な階層的分解が、従来の対称的なアプローチよりも厳密に優れた競争比をもたらすことを実証している。