Parameterized complexity of Strip Packing and Minimum Volume Packing

Abstract

We study the parameterized complexity of Minimum Volume Packing and Strip Packing. In the two dimensional version the input consists of a set of rectangles S with integer side lengths. In the Minimum Volume Packing problem, given a set of rectangles S and a number k, the goal is to decide if the rectangles can be packed in a bounding box of volume at most k. In the Strip Packing problem we are given a set of rectangles S, numbers W and k; the objective is to find if all the rectangles can be packed in a box of dimensions W × k. We prove that the 2-dimensional Volume Packing is in FPT by giving an algorithm that runs in (2 · √2)^k · k^O(1) time. We also show that Strip Packing is W[1]-hard even in two dimensions and give an FPT algorithm for a special case of Strip Packing. Some of our results hold for the problems defined in higher dimensions as well