我们研究了具有任意正开启成本的随机顺序模型中的在线度量设施选址问题。已知一组候选设施及其成本，而对手则固定一个以均匀随机顺序到达的需求点多重集。在这一环境下，我们提出了一个已知时间范围内的确定性 $4.2674$ 竞争算法，显著改善了非均匀开启成本下的 $33$ 倍竞争因子。在排名 $t$ 时，算法使用正归一化排名 $q_t=t/n$，选择一个使得 $d(x,y)+\lambda_t f_y$ 最小化的候选设施，其中 $\lambda_t=\min\left\{1,\frac{q_t}{\mu}\right\}$，并在当前连接距离覆盖此惩罚目标时开启该设施。该分析利用单调一轮收费和上包络分解来控制后续点和每个最优簇的第一个点。对于单位开启成本，该规则精确简化为最近候选设施的距离改善的截止规则。附录中提供了更精细的分析，涉及相关的零开始排名截止，并获得了低于 $3.2805$ 的比率。我们还证明了任意随机在线算法的 $3-o(1)$ 下界。该下界在给定候选集上均匀成本的情况下成立，并在不损失一般性的情况下转移到具有非均匀开启成本的有限全空间模型。结合最近在全空间均匀成本下低于 $2.42$ 的竞争比，这清晰地分隔了全空间均匀与非均匀成本模型的表现。
博主点评： 本文通过引入随机顺序模型，显著提升了在线设施选址的算法效率，特别是针对非均匀开启成本的场景，展示了更优的竞争比。这为未来的算法设计提供了新的思路，同时也揭示了均匀与非均匀成本模型之间的本质差异，值得深入研究与探索。