Computer Science – Data Structures and Algorithms
Scientific paper
2010-10-21
Computer Science
Data Structures and Algorithms
24 pages, 10 figures; full version of extended abstract that appeared in WADS 2009
Scientific paper
We analyze the problem of packing squares in an online fashion: Given a semi-infinite strip of width 1 and an unknown sequence of squares of side length in [0,1] that arrive from above, one at a time. The objective is to pack these items as they arrive, minimizing the resulting height. Just like in the classical game of Tetris, each square must be moved along a collision-free path to its final destination. In addition, we account for gravity in both motion (squares must never move up) and position (any final destination must be supported from below). A similar problem has been considered before; the best previous result is by Azar and Epstein, who gave a 4-competitive algorithm in a setting without gravity (i.e., with the possibility of letting squares "hang in the air") based on ideas of shelf-packing: Squares are assigned to different horizontal levels, allowing an analysis that is reminiscent of some bin-packing arguments. We apply a geometric analysis to establish a competitive factor of 3.5 for the bottom-left heuristic and present a 34/13=2.615...-competitive algorithm.
Fekete Sandor P.
Kamphans Tom
Schweer Nils
No associations
LandOfFree
Online Square Packing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Online Square Packing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Square Packing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-423847