New results on next fit and first fit on-line algorithms for square and rectangle packing

Rectangle packing is a well studied NP-complete problem in which smaller rectangles are packed in an enclosing larger rectangle to minimize wastage of space. Rectangle packing is used in many applications such as scheduling of jobs, allocating memory, VLSI floor planning, pixel art and mobile components packing. In this paper, we study and analyze two online rectangle packing algorithms such as Next Fit and Fit Fit. We obtain interesting constant competitive ratios for square and rectangle packing. Our analytical results shows that FF performs better than NF for both square and rectangle packing for special classes of inputs.