Linda Kleist (Universität Potsdam): Online Sorting and Translational Packing of Convex Polygons

Abstract:
We encounter packing problems on a daily basis, e.g., when organizing our kitchen drawer, baking cookies, cutting fabric, packing a suitcase or the trunk of a car. Clearly, numerous packing problems are also present in industrial settings such as shipping, clothing industry, logistics, etc. 

In this talk, we discuss various translational online packing problems in which convex polygons arrive one by one and have to be placed irrevocably into a horizontal strip (or bins, a square, the plane) 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 width, the number of bins, etc. 

We prove the non-existence of asymptotic constant competitive algorithms for various online translational packing problems of convex polygons, among them strip packing and bin packing. These results remain true, even if the diameter of all pieces is bounded by any small constant ε > 0 and are in stark contrast to the case when either (1) the pieces are restricted to *rectangles* or (2) to the *offline* version of convex polygons, for which online competitive algorithms and offline approximation algorithms with constant ratios are known, respectively. 

The talk is based on joint work with Anders Aamand, Mikkel Abrahamsen, and Lorenzo Beretta.

Before this lecture, from 4:45 p.m., there will be coffee and tea again in room 1404. Everyone is warmly invited to attend.

signed Prof. Dr. Torsten Mütze