A Nearly Quadratic Improvement for Memory Reallocation
<|reference_start|>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-\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$).<|reference_end|>
@article{farach-colton2024a,
    title={A Nearly Quadratic Improvement for Memory Reallocation},
    author={Martin Farach-Colton, William Kuszmaul, Nathan Sheffield, and Alek
  Westover},
    journal={arXiv preprint arXiv:2405.12152},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.12152},
    primaryClass={cs.DS}
}