2026-07-25T14:26:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8800 2024-03-06T10:42:41Z ddc:004 open_access

On the Exact Complexity of Polyomino Packing Bodlaender, Hans L. van der Zanden, Tom C. polyomino packing exact complexity exponential time hypothesis We show that the problem of deciding whether a collection of polyominoes, each fitting in a 2 x O(log n) rectangle, can be packed into a 3 x n box does not admit a 2^{o(n/log{n})}-time algorithm, unless the Exponential Time Hypothesis fails. We also give an algorithm that attains this lower bound, solving any instance of polyomino packing with total area n in 2^{O(n/log{n})} time. This establishes a tight bound on the complexity of Polyomino Packing, even in a very restricted case. In contrast, for a 2 x n box, we show that the problem can be solved in strongly subexponential time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hans L. Bodlaender and Tom C. van der Zanden 2018 Is Part Of LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2018.9 urn:nbn:de:0030-drops-88001 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.9 eng https://creativecommons.org/licenses/by/3.0/legalcode