Zvika Geft: Fully Packed and Ready to Go

9/30/2025 NYU CG Seminar



We consider an ordered storage and retrieval problem: a set of uniform-sized, labeled loads (e.g., containers, pallets, or totes) must be placed in a 2D grid storage area as they arrive sequentially, and then be retrieved in some (possibly different) order. Each load occupies a grid cell and may be moved, e.g., by a robot, along the cardinal directions. Such storage systems arise in logistics, industrial, and transportation domains, where space utilization and retrieval time are critical metrics. To maximize space utilization, loads must be densely packed with some loads blocking access to others, which raises a key question: How should one store the loads to minimize costly rearrangements, i.e., number of relocated loads, during retrieval?

We identify conditions, alongside efficient algorithms, for achieving either zero or near-optimal rearrangements under different knowledge assumptions. While the online case (i.e., no prior knowledge of the storage and retrieval sequences) induces a trade-off between density and rearrangement, we show that even partial prior knowledge essentially eliminates the trade-off. When sequences are fully known, we further provide an intriguing characterization: rearrangement can always be eliminated if the grid’s open side (used to access the loads) is at least 3 cells wide, even for full capacity storage. We also discuss other practical properties of our solutions.

This is a joint work with Kostas Bekris and Jingjin Yu.