Paper Info
Title
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⋅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.
Year
DOI
Venue
2017
10.1016/j.tcs.2016.11.034
Theoretical Computer Science
Keywords
Field
DocType
Strip Packing,Volume minimization,Greedy packing
Integer,Discrete mathematics,Combinatorics,Parameterized complexity,Packing problems,Square packing in a square,Set packing,Circle packing,Strip packing,Mathematics,Minimum bounding box
Journal
Volume
ISSN
Citations 
661
0304-3975
0
PageRank 
References 
Authors
0.34
11
4
Name
Order
Citations
PageRank
Pradeesha Ashok1116.11
Sudeshna Kolay22512.77
Syed Mohammad Meesum300.68
Saket Saurabh42023179.50