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(ϵ-1) 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 ϵ4-fraction of memory, it is possible to achieve expected update cost O(logϵ-1). 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 ϵ-1) 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ϵ-1). 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ϵ-1 ) expected update cost, even in the "large-item"parameter regime (δ> ϵ4).