Online Sorting and its Connection to Geometric Packing Problems

Abstract: We investigate various online packing problems in which convex polygons arrive one by one and have to be placed irrevocably into a container before the next piece is revealed; the pieces must not be rotated, but only translated. The aim is to minimize the used space depending on the specific problem at hand, e.g., the strip length in strip packing, the number of bins in bin packing, etc.

We draw interesting connections to the following online sorting problem: We receive a stream of real numbers $s_1, \cdots ,s_n,$ each from the unit interval $[0,1],$ one by one. Each real must be placed in an array with n initially empty cells without knowing the subsequent arriving reals. The goal is to minimize the sum of differences of consecutive reals in A. The offline optimum is to place the reals in sorted order, so the cost is at most 1. We will see that no online algorithm can achieve a cost lower than $n^{(1/2)}$ in the worst case.

We use such lower bound to answer several fundamental questions about packing. Specifically, we prove the non-existence of competitive algorithms for various online packing problems. A surprising corollary is that no online algorithm can pack translates of convex polygons into a unit square even if we are guaranteed that the total area of the pieces is at most 0.000001 and the diameter of each piece is at most 0.000001.

Computer scienceMathematicsPhysics

Audience: researchers in the topic

MIT Simple Person's Applied Mathematics Seminar