We consider the problem of online packing of convex polygons into a strip through translations. While online algorithms with a constant competitive ratio have been known for rectangles for decades [Baker and Schwarz, SICOMP 1983], the current best algorithm for convex polygons has a competitive ratio of $O(n^{\log_2 3-1}\log n) = O(n^{0.59})$, where $n$ is the number of polygons. This algorithm was described by Aamand, Abrahamsen, Beretta, and Kleist [SODA 2023], who also proved a lower bound of $\Omega(\sqrt{\frac{\log n}{\log\log n}})$ on the competitive ratio of any algorithm. Their lower bound is obtained via a reduction from online sorting, a problem introduced in the same paper, for which they established a lower bound on the competitive ratio. We introduce a new, natural online problem called online TSP scheduling. Here, points $x_1,\ldots,x_n$ arrive online from a metric space $(M,d)$, and upon arrival each $x_i$ must be assigned a visit time $p_i \in [0,\infty)$ satisfying $|p_i-p_j| \ge d(x_i,x_j)$ for all $j$. This provides a new perspective and methods for the online packing problem.
Blogger's Review: This research not only explores the traditional online packing problem but also introduces the concept of online TSP scheduling, showcasing the potential of online algorithms in geometric optimization. The optimization of competitive ratios for convex polygons offers new insights for future algorithm design, making it worth the attention.