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 - 9:1-9:10
BT - 9th International Conference on Fun with Algorithms, FUN 2018
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 9th International Conference on Fun with Algorithms, FUN 2018
Y2 - 13 June 2018 through 15 June 2018
ER -