BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Anders Aamand (MIT CSAIL) DTSTART:20220428T220000Z DTEND:20220428T230000Z DTSTAMP:20260423T035413Z UID:SPAMS/17 DESCRIPTION:Title: O nline Sorting and its Connection to Geometric Packing Problems\nby And ers Aamand (MIT CSAIL) as part of MIT Simple Person's Applied Mathematics Seminar\n\nLecture held in Room: 2 - 132 in the Simons Building.\n\nAbstra ct\nWe investigate various online packing problems in which convex polygon s arrive one by one and have to be placed irrevocably into a container bef ore 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 specif ic problem at hand\, e.g.\, the strip length in strip packing\, the number of bins in bin packing\, etc. \n\n\nWe draw interesting connections to th e 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. E ach real must be placed in an array with n initially empty cells without k nowing the subsequent arriving reals. The goal is to minimize the sum of d ifferences 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 onli ne algorithm can achieve a cost lower than $n^{(1/2)}$ in the worst case. \n\n\nWe use such lower bound to answer several fundamental questions abou t packing. Specifically\, we prove the non-existence of competitive algori thms for various online packing problems. A surprising corollary is that n o online algorithm can pack translates of convex polygons into a unit squa re 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.\n LOCATION:https://researchseminars.org/talk/SPAMS/17/ END:VEVENT END:VCALENDAR