On the exact complexity of polyomino packing

Hans L. Bodlaender, Tom C. Van Der Zanden

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

We show that the problem of deciding whether a collection of polyominoes, each fitting in a 2×O(log n) rectangle, can be packed into a 3×n box does not admit a 2o(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 2O(n/logn) time. This establishes a tight bound on the complexity of Polyomino Packing, even in a very restricted case. In contrast, for a 2 × n box, we show that the problem can be solved in strongly subexponential time.

Original languageEnglish
Title of host publication9th International Conference on Fun with Algorithms, FUN 2018
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages9:1-9:10
ISBN (Electronic)9783959770675
DOIs
Publication statusPublished - 1 Jun 2018
Event9th International Conference on Fun with Algorithms, FUN 2018 - La Maddalena Island, Italy
Duration: 13 Jun 201815 Jun 2018

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume100

Conference

Conference9th International Conference on Fun with Algorithms, FUN 2018
Country/TerritoryItaly
CityLa Maddalena Island
Period13/06/1815/06/18

Keywords

  • Exact complexity
  • Exponential time hypothesis
  • Polyomino packing

Fingerprint

Dive into the research topics of 'On the exact complexity of polyomino packing'. Together they form a unique fingerprint.

Cite this