Almost Online Square Packing
Shahin Kamali, Alejandro López-Ortíz · Canadian Conference on Computational Geometry · 2014
In the square packing problem, the goal is to pack squares of dierent sizes into the smallest number of bins (squares) of uniform size. We introduce an almostonline square packing algorithm which places squares in an online, sequential manner. In doing so, it receives advice of logarithmic size from an oine oracle which runs in linear time. Our algorithm achieve a competitive ratio of at most 1:84 which is signicantly better than the best existing online algorithm which has a competitive ratio of 2.1187. In introducing the algorithm, we have been inspired by the advice model for the analyses of online problems. Our algorithm can also be regarded as a streaming algorithm which packs an input sequence of squares in two passes using a space of logarithmic size.