# Online Sorting and Translational Packing of Convex Polygons

### Wednesday, December 1st, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)

### Mikkel Abrahamsen, University of Copenhagen

### Abstract:

Packing problems regularly appear in everyday life and also in industrial

settings such as shipping, production of clothing, sheet metal cutting, etc. In

this talk, 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, \ldots, s_n$, $s_i \in [0,1]$, one by one.

Each real must be placed in an array $A$ with $Cn$ initially empty cells

without knowing the subsequent reals, for a constant $C\geq 1$. The goal is to

minimize the sum of differences of consecutive reals in $A$. It follows that

the offline optimum is to place the reals in sorted order so the cost is at

most $1$. We show that there is no competitive algorithm for this problem.

We use this lower bound to answer several fundamental questions about packing.

Specifically, we prove the non-existence of competitive algorithms for various

online translational packing problems of convex polygons, among them strip

packing, bin packing and perimeter packing.

Joint work with: Anders Aamand, Lorenzo Beretta, Linda Kleist.