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

标题： 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) 提出，以及在 (对抗性) 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).