技術的概要：確率的到着を伴うオンライン非重心クラスタリングにおける遅延割り当て

1. 問題定義

本論文は、「遅延を伴うオンライン非重心クラスタリング（OCD）」問題を導入し、研究する。この問題は、古典的なクラスタリングのパラダイムを、有限距離空間 $M = (X, d)$ において要素（点）が逐次到着するオンライン設定に拡張したものである。

主要な特徴:

• 非重心クラスタリング: 重心ベースのクラスタリング（例：k-means）とは異なり、クラスタは中心点によって定義されない。代わりに、目的は同一クラスタ内のすべての点間のペアごとの距離の和を最小化することである。これは、エージェントがリーダーだけでなく、グループのすべてのメンバーとの近接性を好む、チーム編成やライドシェアリングなどのシナリオをモデル化する。
• 固定サイズ制約: 本論文は、$\sum n_m = n$ となる所定のクラスタサイズ $\{n_m\}_{m \in [k]}$ を持つクラスタリングに焦点を当てる。これにより、単一要素（シングルトン）のような自明な解を避け、車両の制限やチームサイズなどの現実世界の容量制約を反映させる。
• 遅延割り当て: 時刻 $t_i$ に到着した点の位置 $\ell_i$ が明らかになる。アルゴリズムは直ちに点を割り当てることを強制されない。割り当てを後の時刻 $s_i \ge t_i$ まで延期することができ、その際遅延コスト $w_i = s_i - t_i$ を負う。
• コスト関数: クラスタリングの総コストは、接続コスト（クラスタ内のペアごとの距離）と遅延コストの和である。重要なのは、単一ポイントの遅延コストが、そのクラスタ内の他のすべてのメンバーの接続コストに影響を与えることである（例：ゲームにおいて、一人のプレイヤーの待機がチーム全体の開始を遅らせる）。同一クラスタ内のペア $i, j$ に対するコストは $d(\ell_i, \ell_j) + w_i + w_j$ である。
• 確率的到着モデル: 本論文は未知の i.i.d.（UIID）モデルの下で動作する。点は、有限距離空間上の未知かつ固定された確率分布から、時間とともに独立して到着する。これは、この問題に対して定数競争比を達成するオンラインアルゴリズムが存在しない古典的な最悪ケース（敵対的）モデルとは対照的である。

性能指標:
アルゴリズムの性能は、**期待値比（RoE）**によって測定される。アルゴリズム $A$ が $c$-競争的であるとは、以下の式が成り立つことを意味する：
$$\text{RoE}(A) = \lim_{n \to \infty} \frac{\mathbb{E}[\text{Cost}(A)]}{\mathbb{E}[\text{Cost}(\text{OPT})]} \le c$$
ここで、期待値はランダムな到着列およびアルゴリズムの内部ランダム性に対して取られる。

2. 手法：DGREEDY アルゴリズム

著者は、DGREEDY（Delayed Greedy）と呼ばれる決定論的かつ貪欲なアルゴリズムを提案する。このアルゴリズムは、各時刻 $t$ において、新たに到着した点と「保留中」の点（まだ割り当てられていない点）の両方を考慮して点を処理する。

アルゴリズムの論理:
任意の保留中の点 $i$ に対して、DGREEDY は候補となる行動の 2 つの集合を特定する：

1. 既存クラスタ（$S_i$）: まだ満杯になっていない（$|C_m| < n_m$）既存クラスタ $C_m$ の集合であり、かつ幾何学的条件を満たすもの：点 $i$ からクラスタ内の任意のメンバー $j \in C_m$ までの距離が、$i$ の待ち時間と $j$ の遅延コストの和以下である（$d(\ell_i, \ell_j) \le (t - t_i) + w_j$）。
2. 保留中のペア（$D_i$）: 少なくとも 2 つの保留中の点がある場合、アルゴリズムは、それらの合計待ち時間が距離を超えている（$d(\ell_i, \ell_j) \le (t - t_i) + (t - t_j)$）場合に限り、空のクラスタスロットにペア $(i, j)$ で新しいクラスタを形成することを検討する。

決定ルール:

• $S_i$ が空でない場合、アルゴリズムは総コストの増加を最小化するクラスタ $m_1$ を選択する。
• $D_i$ が空でない場合、コストの増加を最小化するペア $(j, m_2)$ を選択し、同点の場合はペアの総待ち時間を最大化することでタイを破る（コストが無限に増大するのを防ぐため）。
• 最終割り当て: アルゴリズムは、最良の既存クラスタオプション（$m_1$）と最良の新しいペアオプション（$m_2$）を比較する。総コストの増加がより低い割り当てを実行する。どちらが選択されない場合、点 $i$ は待ち続ける。

幾何学的解釈:
このアルゴリズムは、保留中の点を中心とした球が拡大する様子として視覚化できる。球の半径は時間とともに成長し（遅延コストを表す）、保留中の点の球が既存クラスタ内の点の球、あるいは他の保留中の点の球と交差した時点で割り当てが発生する。

3. 主要な貢献と結果

理論的保証

主な貢献は、UIID モデルの下でDGREEDY が定数の期待値比を達成することの証明である。

• DGREEDY の上限: 著者は、DGREEDY の期待総コストの上限を導出する。点は、到着時の特定の半径 $r_x$（分布と距離空間の性質によって定義される）内で割り当てられるかどうかに基づいて、「早期点」と「後期点」に分類される。

  • 早期点: その遅延は半径 $r_x$ によって制限される。
  • 後期点: その遅延は距離空間の直径によって制限されるが、著者はそのような点が最大 $|X|$（有限）個であることを証明する。
  • 総期待コストは $O(n)$ であることが示される。

• OPT の下限: 著者は、最適オフライン解（OPT）の期待コストの下限を確立する。各点の最小コスト $c_i(\sigma)$ を分析し、確率的設定では、点ごとの期待最小コストがその局所近傍の確率質量に反比例することを示す。これもまた $O(n)$ の下限をもたらす。

• 定数競争比: DGREEDY の上限と OPT の下限を比較することにより、著者は以下を証明する：
  $$\lim_{n \to \infty} \frac{\text{DGREEDY}(I)}{\text{OPT}(I)} \le \frac{8(n_1 - 1)}{(n_k - 1)(1 - e^{-2})}$$
  すべてのクラスタサイズが等しい場合（$n_m = n'$）、比は定数に簡略化される：
  $$\lim_{n \to \infty} \frac{\text{DGREEDY}(I)}{\text{OPT}(I)} \le \frac{8}{1 - e^{-2}} \approx 12.5$$
  この結果は、最悪ケースモデルでは競争比が対数未満または無界であるのに対し、確率的モデルでは定数競争アルゴリズムが可能であることを示している。

拡張

本論文は、理論的枠組みが以下に拡張可能であることを示している：

1. 非距離空間: 対称化による非対称距離、および最短経路距離による三角不等式を満たさない空間に対して、アルゴリズムと解析が成り立つ。
2. ヘドニックゲーム: このモデルは、エージェントが同盟メンバーに対して選好を持つ、エージェントタイプを伴うオンライン加法的分離ヘドニックゲーム（ASHGs）に直接マッピングされる。
3. 可変クラスタサイズ: 結果は、クラスタサイズに下限と上限（$l_m \le |C_m| \le u_m$）が存在する場合にも拡張可能であり、その際これらの境界が定数であればよい。

4. 意義と主張

本論文は、「最悪ケースの敵対者を超えた希望」を提供すると主張する。その意義は以下の点にある：

• ギャップの埋め合わせ: ゲーム内のチーム編成、ライドシェアリング、フェデレーテッドラーニングなどの現実的な応用に関連する、遅延を伴うオンライン非重心クラスタリングに関する研究の欠如に対処している。
• 不可能性の克服: 定数競争比が存在しないという最悪ケースモデルの強い不可能性結果が、確率的到着過程（UIID）を仮定することで回避可能であることを示している。
• 実用性: $n \to \infty$ における期待値比に焦点を当てることで、本論文は小規模で病理的な最悪ケース入力ではなく、大規模かつ実用的なシナリオをターゲットとしている。
• アルゴリズムの単純さ: 提案された DGREEDY アルゴリズムは決定論的かつ貪欲であり、この確率的設定において定数競争を達成するために複雑な確率的または学習ベースのアプローチが不要であることを示唆している。

著者は、この研究が一般的な遅延コスト関数、既知または時間変化する分布、およびクラスタリングをペナルティ付きで変更可能な設定に関する将来の研究への道を開くと結論付けている。