Parameterized complexity of Strip Packing and Minimum Volume Packing

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⋅kO(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.