A Nearly Quadratic Improvement for Memory Reallocation

In the Memory Reallocation Problem a set of items of various sizes must be dynamically assigned to non-overlapping contiguous chunks of memory. It is guaranteed that the sum of the sizes of all items present at any time is at most a (1-ε)-fraction of the total size of memory (i.e., the load-factor is at most 1-ε). The allocator receives insert and delete requests online, and can re-arrange existing items to handle the requests, but at a reallocation cost defined to be the sum of the sizes of items moved divided by the size of the item being inserted/deleted. The folklore algorithm for Memory Reallocation achieves a cost of O(ε⁻¹) per update. In recent work at FOCS'23, Kuszmaul showed that, in the special case where each item is promised to be smaller than an ε⁴-fraction of memory, it is possible to achieve expected update cost O(logε⁻¹). Kuszmaul conjectures, however, that for larger items the folklore algorithm is optimal. In this work we disprove Kuszmaul's conjecture, giving an allocator that achieves expected update cost O(ε-1/2 *polylog ε⁻¹) on any input sequence. We also give the first non-trivial lower bound for the Memory Reallocation Problem: we demonstrate an input sequence on which any resizable allocator (even offline) must incur amortized update cost at least Ω(logε⁻¹). Finally, we analyze the Memory Reallocation Problem on a stochastic sequence of inserts and deletes, with random sizes in [δ, 2 δ] for some δ. We show that, in this simplified setting, it is possible to achieve O(logε⁻¹) expected update cost, even in the ``large item'' parameter regime (δ > ε⁴).