💻 computer science

A 2.37332-Competitive Algorithm for Online Square Packing with Gravity

This paper introduces the $\mathrm{AsymmetricSlots}$ algorithm, which achieves a 2.37332-competitive ratio for online square packing in a unit-width strip under Tetris and gravity constraints, improving upon the previous best bound of approximately 2.6154 while also establishing optimal dependence on aspect ratio for general rectangles.

Original authors: Nichlas Langhoff Rasmussen

Published 2026-09-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nichlas Langhoff Rasmussen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where you must build a tower, one block at a time, without ever seeing what comes next. You cannot rearrange the blocks you have already placed, and you cannot reach into the structure to move them aside. Every new block must drop from above, falling straight down until it hits the top of the existing pile or the floor. If a gap exists in the tower, but it is blocked from above by a wider block, that gap is useless; nothing can ever reach it. This is the challenge of online packing under gravity, a problem that sits at the intersection of geometry and logistics. It asks a simple but stubborn question: how can a system make the best possible decisions when it is blind to the future and bound by the laws of physics?

For years, the best known method for stacking square blocks in this manner could guarantee a tower no more than about 2.62 times taller than the absolute shortest tower possible if one had seen all the blocks in advance. This gap between the online reality and the offline ideal represented a significant inefficiency. Researchers had long suspected that a smarter way to organize the space might close this gap, but the constraints of gravity and the lack of foresight made finding such a method exceptionally difficult. The problem is not just about fitting shapes together; it is about managing the flow of space as it is consumed, ensuring that the path for future blocks remains open even as the current structure grows.

A recent study introduces a new strategy called AsymmetricSlots, which successfully tightens this efficiency gap. The researchers developed a method that improves the worst-case performance of the packing algorithm, proving that the resulting tower will never be more than approximately 2.37 times the height of the perfect, pre-planned tower. This is a measurable improvement over the previous best result, bringing the theoretical limit of online square packing significantly closer to the ideal. The work does not claim to have solved the problem entirely, as a gap remains between this new upper limit and the known lower limit of 2, but it establishes a new, higher standard for what is achievable.

The core of this new approach lies in how the available space is divided. Previous methods treated the vertical strip of space as a series of equal-sized, nested compartments, splitting the width in half at every level. The new algorithm breaks this symmetry. Instead of splitting the space evenly, it divides every available slot into two unequal children: one wide and one narrow. When a new square arrives, the algorithm decides where to send it based on its size relative to these unequal divisions. If a square is too large for the narrow child, it is forced into the wide child. If it is small enough to fit in both, the algorithm sends it to whichever child currently has the lower stack of blocks. This local decision-making process, repeated as the square descends through the hierarchy of slots, allows the system to balance the load more effectively than the old symmetric methods.

To prove that this strategy works, the researchers used a method of accounting that tracks the "cost" of every square placed. They imagined that each square pays for the height it adds to the tower using its own area as currency. Large squares, which are forced into specific slots, pay for their own height directly. Smaller squares, which have the flexibility to choose between slots, are handled through a system of temporary credits that balance out over time. The analysis shows that the loss of efficiency caused by these flexible choices does not accumulate as the tower grows taller; instead, it remains bounded. This mathematical proof confirms that the algorithm's performance is stable and predictable, regardless of the sequence of blocks it receives.

The study also extends this logic to rectangles that are not perfect squares, but are limited in how long and thin they can be. For these shapes, the researchers found that the efficiency of the packing depends directly on the maximum ratio of a rectangle's length to its width. They proved that as this ratio increases, the difficulty of packing increases in a predictable, linear fashion. This result suggests that the method is robust and can be adapted to a wider variety of shapes, provided the shapes do not become infinitely thin. Conversely, they also demonstrated that no online algorithm can do significantly better than this linear relationship, meaning the dependence on the shape's proportions is fundamental to the problem itself.

While the new algorithm represents a significant step forward, the researchers are careful to note that the problem is not yet fully solved. They constructed specific scenarios where their new algorithm produces a tower twice as tall as the optimal offline solution, showing that the gap between the best possible online performance and the theoretical ideal is still substantial. The difference between the new upper limit of roughly 2.37 and the lower limit of 2 remains a wide chasm for mathematicians to bridge. However, by establishing a new, tighter bound and providing a framework that handles both squares and bounded rectangles, this work clarifies the landscape of the problem. It shows that with the right kind of asymmetric organization, the constraints of gravity and ignorance of the future can be managed with greater precision than previously thought possible.

Technical Summary: A 2.37332-Competitive Algorithm for Online Square Packing with Gravity

Problem Definition
The paper addresses the online strip packing problem for axis-parallel squares under Tetris and gravity constraints. In this model, squares arrive sequentially without knowledge of future items and must be placed irrevocably into a unit-width strip of unbounded height.

Tetris Constraint: An incoming square must follow a collision-free, monotonic downward path from above to its final position.
Gravity Constraint: The square must come to rest on the strip bottom or on the top surface of previously placed squares.
Feasibility: A geometrically empty region may be unusable if it is unreachable via a downward path or lacks support.

The objective is to minimize the total height of the packing. The performance is measured by the asymptotic competitive ratio ( $CR$ ), defined as the infimum of $\rho$ such that $A(\sigma) \le \rho \cdot OPT(\sigma) + \beta$ for all input sequences $\sigma$ , where $A(\sigma)$ is the algorithm's height and $OPT(\sigma)$ is the optimal offline height.

Methodology: AsymmetricSlots
The author introduces AsymmetricSlots, a recursive algorithm that improves upon the previous best-known approach, SlotAlgorithm (Fekete et al., 2014), which used a dyadic (symmetric) hierarchy.

Asymmetric Hierarchy:
Instead of splitting a slot of width $w$ into two equal halves, the algorithm splits it into a wide child of width $pw$ and a narrow child of width $qw$, where $p \in (1/2, 1)$ and $q = 1-p$ . This hierarchy is fixed before any items arrive.
Local Routing Rules:
Upon arrival, a square of side $a$ descends the hierarchy based on its size relative to the current slot width $w$ :
- Direct: If $a > pw$, the square is assigned to the current slot immediately.
- Forced: If $qw < a \le pw$ , the square is forced into the wide child.
- Flexible: If $a \le qw$ , the square is routed to the child with the smaller current virtual height (with ties broken in favor of the wide child).
Virtual Height Profile & Feasibility:
The algorithm maintains a piecewise-constant virtual height profile $h(x)$ to guide routing. A square assigned to a slot $T$ updates the virtual height of that slot's interval by its side length $a$ .
- Lemma 1 proves that despite the virtual profile potentially overestimating the physical height, the physical insertion is always feasible under Tetris and gravity constraints. Specifically, the physical square can always fall to a support level $y^*$ (determined by existing squares or the strip bottom) that is $\le$ the virtual update level, ensuring no collisions occur during descent.
Analysis via Local Charging:
The proof utilizes a local phase invariant and a charging argument that exploits the asymmetry of the split:
- Forced Squares: Large squares ($a > qw$) are forced into specific paths. Their area is sufficient to "pay" for the height they create ( $wa - \rho a^2 \le 0$ ).
- Flexible Squares: Small squares ( $a \le qw$ ) allow for balancing between children. The analysis uses a "phase-based" accounting where the algorithm maintains a credit $\delta w^2$ . The asymmetry ensures that the loss associated with flexible placements is bounded locally and does not accumulate with the depth of the hierarchy.
- Phase Closure: A phase at a slot ends when a "direct" square (one too large for the children) is placed, resetting the virtual profile.

Key Results

Improved Upper Bound for Squares:
By optimizing the split parameter $p$ , the author derives a competitive ratio of 2.373318506....
- The optimal parameter $p^\star$ is the unique root in $(1/2, 1)$ of $16p^3 - 8p^2 + p - 1 = 0$ , yielding $p^\star \approx 0.5786$ .
- The resulting ratio is $\rho^\star = 1/(1-p^\star) \approx 2.3733$ .
- A rational approximation using $p = 11/19$ yields a clean ratio of 2.375 ( $19/8$ ).
- This improves the previous best upper bound of $34/13 \approx 2.6154$ established by Fekete et al.
Lower Bound for the Algorithm:
The paper establishes a specific lower bound for AsymmetricSlots. Using a repeated-square construction, they show that for $p$ in a range containing $p^\star$ , the competitive ratio is at least 2.
- Thus, $2 \le CR(AsymmetricSlots_{p^\star}) \le 2.3733...$
- The general lower bound for any deterministic online algorithm in this model remains $3/2$ (from Fekete et al.).
Extension to Rectangles:
The framework is extended to rectangles with a bounded aspect ratio $\kappa$ (where width $u$ and height $v$ satisfy $u/\kappa \le v \le \kappa u$ ).
- Upper Bound: The algorithm achieves an asymptotic competitive ratio of $O(\kappa)$ .
- Lower Bound: A matching $\Omega(\kappa)$ lower bound is proven via an alternating construction of thin vertical and wide shallow rectangles.
- This establishes that the optimal dependence on the aspect ratio is $\Theta(\kappa)$ .

Significance and Claims
The paper claims to provide the best known upper bound for the online square packing problem with Tetris and gravity constraints, reducing the competitive ratio from $\approx 2.6154$ to $\approx 2.3733$ .

Methodological Contribution: The shift from a symmetric (dyadic) to an asymmetric recursive decomposition allows for a more efficient local charging argument. The asymmetry separates placements into "forced" (large) and "flexible" (small) categories, preventing the accumulation of error terms that plagued previous analyses.
Scope: The results are strictly theoretical, focusing on the competitive analysis of deterministic algorithms. The paper does not claim to solve the general offline problem or provide a polynomial-time approximation scheme for the offline case.
Limitations: The author notes that the gap between the algorithm-specific lower bound (2) and the upper bound (2.3733) remains, as does the gap between the general lower bound (1.5) and the upper bound. The paper suggests that future work could explore non-self-similar splits or more than two subslots to potentially close these gaps.

In summary, the work refines the theoretical limits of online square packing under physical constraints, demonstrating that asymmetric hierarchical decomposition yields a strictly better competitive ratio than previously known symmetric approaches.

Technical Summary: A 2.37332-Competitive Algorithm for Online Square Packing with Gravity

More like this