技术摘要：随机到达下在线非质心聚类中的延迟分配

1. 问题定义

本文引入并研究了**带延迟的在线非质心聚类（OCD）**问题。该问题将经典聚类范式扩展至在线场景，其中元素（点）在有限度量空间 $M = (X, d)$ 中按顺序到达。

关键特征：

• 非质心聚类： 与基于中心的聚类（如 k-means）不同，聚类并非由中心点定义。相反，目标是最小化同一聚类内所有点对之间的距离之和。这模拟了团队组建或拼车等场景，其中参与者更倾向于与其组内所有成员保持邻近，而不仅仅是靠近领导者。
• 固定大小约束： 本文关注具有预定聚类大小 $\{n_m\}_{m \in [k]}$ 的聚类，满足 $\sum n_m = n$。这避免了平凡解（如单点聚类），并反映了现实世界中的容量限制（例如车辆限制、团队规模）。
• 延迟分配： 当点在时间 $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$。
• 随机到达模型： 本文在**未知独立同分布（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（延迟贪婪）的确定性贪婪算法。该算法在每个时间步 $t$ 处理点，同时考虑新到达的点和“待处理”点（尚未分配的点）。

算法逻辑：
对于任何待处理点 $i$，DGREEDY 识别两组候选操作：

1. 现有聚类（$S_i$）： 尚未填满（$|C_m| < n_m$）且满足几何条件的现有聚类 $C_m$ 集合：点 $i$ 到 $C_m$ 中任意成员 $j$ 的距离小于或等于 $i$ 的等待时间加上 $j$ 的延迟成本（$d(\ell_i, \ell_j) \le (t - t_i) + w_j$）。
2. 待处理点对（$D_i$）： 如果至少有两个待处理点，算法考虑在空聚类槽中用一对 $(i, j)$ 形成新聚类，前提是它们的组合等待时间超过它们之间的距离（$d(\ell_i, \ell_j) \le (t - t_i) + (t - t_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 算法是确定性和贪婪的，这表明在此随机设置中，实现常数竞争比可能不需要复杂的概率或基于学习的方法。

作者总结道，他们的工作为未来研究一般延迟成本函数、已知或时变分布以及可修改聚类并施加惩罚的场景铺平了道路。