In the Demand Strip Packing problem (DSP), we are given a finite set of axis-aligned rectangular items, each characterized by a specific width and height. These items need to be packed without rotation into a strip of fixed width while minimizing the peak demand: the maximum sum of heights of items placed at any point on the x-axis. We are the first to consider the online variant of the problem, where items are revealed to an algorithm one by one in a list. Upon arrival, each item must be placed on the strip irrevocably before the next item in the list is revealed. As usual in online optimization, we evaluate the performance of online algorithms using competitive analysis. We give a strictly 4.263-competitive algorithm, significantly improving upon the respective bound of 6.479 for Online Strip Packing. Additionally, we prove a lower bound of 1.812 on the absolute competitive ratio of any online algorithm for DSP and, thus, clearly separate Online DSP from Online Minimum Peak Appointment Scheduling (MPAS), a special case of Online DSP, for which a strictly 5/3-competitive algorithm is known.
This is joint work with Franziska Eberle, Georgios Moneftsis, Malin Rau, and Albert Vesterlund.
Sebastian Bruchhold (TU Berlin)
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .