Online Square-into-Square Packing

• Published in: Algorithmica 2017-03, Vol.77 (3), p.867-901
• Main Authors: Fekete, Sándor P., Hoffmann, Hella-Franziska
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Classifying; Computer Science; Computer Systems Organization and Communication Networks; Containers; Data Structures and Information Theory; Mathematics of Computing; Proving; Sequences; Sorting algorithms; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-016-0114-2

In 1967, Moon and Moser proved a tight bound on the critical density of squares in squares: any set of squares with a total area of at most 1/2 can be packed into a unit square, which is tight. The proof requires full knowledge of the set, as the algorithmic solution consists in sorting the objects by decreasing size, and packing them greedily into shelves. Since then, the online version of the problem has remained open; the best upper bound is still 1/2, while the currently best lower bound is 1/3, due to Han et al. (Theory Comput Syst 43(1):38–55, 2008 ). In this paper, we present a new lower bound of 11/32, based on a dynamic shelf allocation scheme, which may be interesting in itself. We also give results for the closely related problem in which the size of the square container is not fixed, but must be dynamically increased in order to accommodate online sequences of objects. For this variant, we establish an upper bound of 3/7 for the critical density, and a lower bound of 1/8. When aiming for accommodating an online sequence of squares, this corresponds to a 2.82 … -competitive method for minimizing the required container size, and a lower bound of 1.33 … for the achievable factor.