我们考虑将凸多边形在线打包到带中的问题，通过平移进行操作。尽管对于矩形的在线算法已经有几十年的研究，且具有常数竞争比 [Baker and Schwarz, SICOMP 1983]，但目前针对凸多边形的最佳算法的竞争比为 $O(n^{\log_2 3-1}\log n) = O(n^{0.59})$，其中 $n$ 是多边形的数量。该算法由 Aamand、Abrahamsen、Beretta 和 Kleist [SODA 2023] 描述，并且他们证明了任何算法的竞争比下限为 $\Omega(\sqrt{\frac{\log n}{\log\log n}})$。他们的下限通过从在线排序问题的一个减小得出，这一问题在同一论文中被介绍，并且为其建立了竞争比的下限。我们引入一个新的、自然的在线问题，称为在线 TSP 调度。在这个问题中，点 $x_1,\ldots,x_n$ 在线从度量空间 $(M,d)$ 中到达，并且一旦到达每个 $x_i$，必须分配一个访问时间 $p_i \in [0,\infty)$，满足 $|p_i-p_j| \ge d(x_i,x_j)$ 对所有 $j$。这样，我们为在线打包问题提供了新的视角和方法。
博主点评： 该研究不仅探讨了在线打包的传统问题，还引入了在线 TSP 调度的概念，展示了在线算法在几何优化中的潜力。凸多边形的竞争比优化为未来的算法设计提供了新的思路，值得关注。