  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-\varepsilon)$-fraction of the total size of memory (i.e., the
load-factor is at most $1-\varepsilon$). 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(\varepsilon^{-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
$\varepsilon^4$-fraction of memory, it is possible to achieve expected update
cost $O(\log\varepsilon^{-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(\varepsilon^{-1/2} \operatorname*{polylog}
\varepsilon^{-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 $\Omega(\log\varepsilon^{-1})$.
  Finally, we analyze the Memory Reallocation Problem on a stochastic sequence
of inserts and deletes, with random sizes in $[\delta, 2 \delta]$ for some
$\delta$. We show that, in this simplified setting, it is possible to achieve
$O(\log\varepsilon^{-1})$ expected update cost, even in the ``large item''
parameter regime ($\delta > \varepsilon^4$).
