Jul 2026
Online Geometric Packing through Online TSP Scheduling
We consider the problem of online packing of convex polygons into a strip by 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 competitive ratio $O(n^{\log_2 3-1}\log n)...
Anders Aamand, Mikkel Abrahamsen, Simon Bartlmae et al.
· arXiv.org · 1 citation