2026-07-22T18:38:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7562 2024-03-06T10:40:37Z ddc:004 open_access

Online Strip Packing with Polynomial Migration Jansen, Klaus Klein, Kim-Manuel Kosche, Maria Ladewig, Leon strip packing bin packing online algorithms migration factor We consider the relaxed online strip packing problem, where rectangular items arrive online and have to be packed into a strip of fixed width such that the packing height is minimized. Thereby, repacking of previously packed items is allowed. The amount of repacking is measured by the migration factor, defined as the total size of repacked items divided by the size of the arriving item. First, we show that no algorithm with constant migration factor can produce solutions with asymptotic ratio better than 4/3. Against this background, we allow amortized migration, i.e. to save migration for a later time step. As a main result, we present an AFPTAS with asymptotic ratio 1 + O(epsilon) for any epsilon > 0 and amortized migration factor polynomial in 1/epsilon. To our best knowledge, this is the first algorithm for online strip packing considered in a repacking model. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Klaus Jansen and Kim-Manuel Klein and Maria Kosche and Leon Ladewig 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.13 urn:nbn:de:0030-drops-75620 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.13 eng https://creativecommons.org/licenses/by/3.0/legalcode