On the Exact Complexity of Polyomino Packing
2020
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 / 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 × n box, we show that the problem can be solved in strongly subexponential time.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
9
References
0
Citations
NaN
KQI