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

32 Downloads (Pure)

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
EditorsH. Ito, S. Leonardi, L. Pagli, G. Prencipe
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages91-910
Number of pages820
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
Conference number: 9

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume100
ISSN (Print)1868-8969

Conference

Conference9th International Conference on Fun with Algorithms (FUN 2018)
Abbreviated titleFUN 2018
CountryItaly
CityLa Maddalena Island
Period13/06/1815/06/18

Keywords

  • Exact complexity
  • Exponential time hypothesis
  • Polyomino packing

Cite this

Bodlaender, H. L., & Van Der Zanden, T. C. (2018). On the exact complexity of polyomino packing. In H. Ito, S. Leonardi, L. Pagli, & G. Prencipe (Eds.), 9th International Conference on Fun with Algorithms, FUN 2018 (pp. 91-910). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 100). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FUN.2018.9
Bodlaender, Hans L. ; Van Der Zanden, Tom C. / On the exact complexity of polyomino packing. 9th International Conference on Fun with Algorithms, FUN 2018. editor / H. Ito ; S. Leonardi ; L. Pagli ; G. Prencipe. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. pp. 91-910 (Leibniz International Proceedings in Informatics (LIPIcs)).
@inproceedings{c027bb4cf0ea406e884b1b3dd3d18b85,
title = "On the exact complexity of polyomino packing",
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.",
keywords = "Exact complexity, Exponential time hypothesis, Polyomino packing",
author = "Bodlaender, {Hans L.} and {Van Der Zanden}, {Tom C.}",
year = "2018",
month = "6",
day = "1",
doi = "10.4230/LIPIcs.FUN.2018.9",
language = "English",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
pages = "91--910",
editor = "H. Ito and S. Leonardi and L. Pagli and G. Prencipe",
booktitle = "9th International Conference on Fun with Algorithms, FUN 2018",

}

Bodlaender, HL & Van Der Zanden, TC 2018, On the exact complexity of polyomino packing. in H Ito, S Leonardi, L Pagli & G Prencipe (eds), 9th International Conference on Fun with Algorithms, FUN 2018. Leibniz International Proceedings in Informatics (LIPIcs), vol. 100, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, pp. 91-910, 9th International Conference on Fun with Algorithms (FUN 2018), La Maddalena Island, Italy, 13/06/18. https://doi.org/10.4230/LIPIcs.FUN.2018.9

On the exact complexity of polyomino packing. / Bodlaender, Hans L.; Van Der Zanden, Tom C.

9th International Conference on Fun with Algorithms, FUN 2018. ed. / H. Ito; S. Leonardi; L. Pagli; G. Prencipe. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. p. 91-910 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 100).

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

TY - GEN

T1 - On the exact complexity of polyomino packing

AU - Bodlaender, Hans L.

AU - Van Der Zanden, Tom C.

PY - 2018/6/1

Y1 - 2018/6/1

N2 - 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.

AB - 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.

KW - Exact complexity

KW - Exponential time hypothesis

KW - Polyomino packing

UR - http://www.scopus.com/inward/record.url?scp=85048970648&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.FUN.2018.9

DO - 10.4230/LIPIcs.FUN.2018.9

M3 - Conference contribution

AN - SCOPUS:85048970648

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 91

EP - 910

BT - 9th International Conference on Fun with Algorithms, FUN 2018

A2 - Ito, H.

A2 - Leonardi, S.

A2 - Pagli, L.

A2 - Prencipe, G.

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl

ER -

Bodlaender HL, Van Der Zanden TC. On the exact complexity of polyomino packing. In Ito H, Leonardi S, Pagli L, Prencipe G, editors, 9th International Conference on Fun with Algorithms, FUN 2018. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2018. p. 91-910. (Leibniz International Proceedings in Informatics (LIPIcs)). https://doi.org/10.4230/LIPIcs.FUN.2018.9