标题： 一个对数次多项式竞争算法用于随机在线排序和旅行商问题 显示英文标题

标题： A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP

摘要： 在\emph{在线排序}中，给出一个初始为空单元格的数组$n$。 在每个时间步$t$，一个元素$x_t \in [0,1]$到达，并必须不可逆地放入一个空单元格，而没有任何未来到达的知识。 我们的目标是使放置在连续数组单元格中的元素对之间的绝对差之和最小化，寻求一种在线放置策略，使得最终数组尽可能接近已排序的数组。 当请求序列由$d$维单位超立方体中的点组成，且目标是使连续单元格中点之间的欧几里得距离之和最小化时，会出现一个有趣的多维推广，即\emph{在线旅行商问题}。 受（Abrahamsen, Bercea, Beretta, Klausen 和 Kozma；ESA 2024）最近工作的启发，我们考虑了在线排序（\textit{分别}在线 TSP）的\emph{随机版本}，其中每个元素（\textit{分别}点）$x_t$是从$[0, 1]$（\textit{分别} $[0,1]^d$ ）上的均匀分布中独立同分布采样的。 通过将请求序列仔细分解为一个球入桶实例的层次结构，其中球与桶的比例足够大，使得桶占用量在均值附近 sharply 集中，又足够小，以便我们可以高效处理放在同一桶中的元素，我们得到一个在线算法，在高概率下以$O(\log^2 n)$的因子近似最优成本。 我们的结果对 Stochastic Online Sorting 之前已知的最佳竞争比$\tilde{O}(n^{1/4})$（由 (Abrahamsen 等人；ESA 2024)）和 (adversarial) Online TSP 的之前已知的最佳竞争比$O(\sqrt{n})$（由 (Bertram, ESA 2025)）做出了指数级的改进。 显示英文摘要

摘要： In \emph{Online Sorting}, an array of $n$ initially empty cells is given. At each time step $t$, an element $x_t \in [0,1]$ arrives and must be placed irrevocably into an empty cell without any knowledge of future arrivals. We aim to minimize the sum of absolute differences between pairs of elements placed in consecutive array cells, seeking an online placement strategy that results in a final array close to a sorted one. An interesting multidimensional generalization, a.k.a. the \emph{Online Travelling Salesperson Problem}, arises when the request sequence consists of points in the $d$-dimensional unit cube and the objective is to minimize the sum of euclidean distances between points in consecutive cells. Motivated by the recent work of (Abrahamsen, Bercea, Beretta, Klausen and Kozma; ESA 2024), we consider the \emph{stochastic version} of Online Sorting (\textit{resp.} Online TSP), where each element (\textit{resp.} point) $x_t$ is an i.i.d. sample from the uniform distribution on $[0, 1]$ (\textit{resp.} $[0,1]^d$). By carefully decomposing the request sequence into a hierarchy of balls-into-bins instances, where the balls to bins ratio is large enough so that bin occupancy is sharply concentrated around its mean and small enough so that we can efficiently deal with the elements placed in the same bin, we obtain an online algorithm that approximates the optimal cost within a factor of $O(\log^2 n)$ with high probability. Our result comprises an exponential improvement on the previously best known competitive ratio of $\tilde{O}(n^{1/4})$ for Stochastic Online Sorting due to (Abrahamsen et al.; ESA 2024) and $O(\sqrt{n})$ for (adversarial) Online TSP due to (Bertram, ESA 2025).