The classic memory‑allocation problem asks how to place objects of varying sizes in memory while minimizing the so‑called memory high‑water mark. Since the early 1970s it has been known that any deterministic online allocator has an optimal competitive ratio of $\Theta(\log M)$, where $M$ denotes the volume high‑water mark of the request sequence.
This paper observes that many real‑world allocators appear to bypass the 1971 lower bound by adopting a slightly different model. They allow $k$‑aggregate request fragmentation: the allocator may split a request into multiple fragments as long as the all‑time maximum number of simultaneous fragments never exceeds $k$ times the all‑time maximum number of simultaneous requests.
The central question is whether request fragmentation fundamentally changes the memory‑allocation problem, and if so, how.
The surprising answer is that even with $k = 1 + o(1)$ fragmentation, the optimal competitive ratio—$\Theta(\log M)$ in the classical setting—collapses to $\Theta(\log \log M)$. This bound is tight, with matching upper and lower bounds for both deterministic and randomized algorithms.
Review: By introducing the $k$‑aggregate fragmentation model, the paper shows that even a tiny allowance for fragmentation can dramatically improve the competitive performance of online memory allocators. This insight has practical implications for designing more efficient allocators and invites further study of fragmentation strategies under diverse workload conditions.