On the exact complexity of polyomino packing

Hans L. Bodlaender; Tom C. Van Der Zanden

doi:10.4230/LIPIcs.FUN.2018.9

On the exact complexity of polyomino packing

Hans L. Bodlaender, Tom C. Van Der Zanden

Algorithms, Geometry and Applications

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

66 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 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/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 language	English
Title of host publication	9th International Conference on Fun with Algorithms, FUN 2018
Editors	H. Ito, S. Leonardi, L. Pagli, G. Prencipe
Place of Publication	Dagstuhl
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	91-910
Number of pages	820
ISBN (Electronic)	9783959770675
DOIs	https://doi.org/10.4230/LIPIcs.FUN.2018.9
Publication status	Published - 1 Jun 2018
Event	9th International Conference on Fun with Algorithms (FUN 2018) - La Maddalena Island, Italy Duration: 13 Jun 2018 → 15 Jun 2018 Conference number: 9

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Volume	100
ISSN (Print)	1868-8969

Conference

Conference	9th International Conference on Fun with Algorithms (FUN 2018)
Abbreviated title	FUN 2018
Country/Territory	Italy
City	La Maddalena Island
Period	13/06/18 → 15/06/18

Keywords

Exact complexity
Exponential time hypothesis
Polyomino packing

Access to Document

10.4230/LIPIcs.FUN.2018.9

publishers versionFinal published version, 481 KBLicence: CC BY

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). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FUN.2018.9

@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 = jun,

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",

note = "9th International Conference on Fun with Algorithms (FUN 2018), FUN 2018 ; Conference date: 13-06-2018 Through 15-06-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 proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On the exact complexity of polyomino packing

AU - Bodlaender, Hans L.

AU - Van Der Zanden, Tom C.

N1 - Conference code: 9

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

T2 - 9th International Conference on Fun with Algorithms (FUN 2018)

Y2 - 13 June 2018 through 15 June 2018

ER -

On the exact complexity of polyomino packing

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this