Metraipolis › archive › dc_0a9eb48efb28

Tight Bounds for Memory Allocation With and Without Request Fragmentation — arXiv:2608.28462

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.28462
License (as archived)
CC0-1.0
Archived
2026-10-17T11:52:26.698Z
SHA-256 of the archived text
5e4547fd229bd5834c9c150355a5c24dbce67e4380ea79d398cc0612cef7ad78
Stable URL of this page
https://metraipolis.com/documento/dc_0a9eb48efb28

How to cite

Tight Bounds for Memory Allocation With and Without Request Fragmentation — arXiv:2608.28462 — arXiv (en), https://arxiv.org/abs/2608.28462 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0a9eb48efb28 (Metraipolis archive dc_0a9eb48efb28, sha256 5e4547fd229bd5834c9c150355a5c24dbce67e4380ea79d398cc0612cef7ad78)
BibTeX
@misc{dc0a9eb48efb28,
  title = {Tight Bounds for Memory Allocation With and Without Request Fragmentation — arXiv:2608.28462},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.28462},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0a9eb48efb28; sha256 5e4547fd229bd5834c9c150355a5c24dbce67e4380ea79d398cc0612cef7ad78},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.28462. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The classical memory-allocation problem captures the task of placing objects of different sizes in memory, while minimizing the so-called memory high-water mark. It has been known since the early 1970s that the optimal competitive ratio for any deterministic online allocator is $\Theta(\log M)$, where $M$ is the volume high-water mark of the underlying request sequence. This paper begins with a simple observation: many real-world allocators seem to bypass the 1971 lower bound by adopting a slightly different model for memory allocation. These allocators use what we call $k$-aggregate request fragmentation, meaning that the memory allocator is permitted to break requests into multiple fragments, so long as the all-time maximum number of simultaneous fragments is at most $k$ times the all-time maximum number of simultaneous requests. We consider the following basic question: Does request fragmentation fundamentally change the problem of memory allocation, and if so, how? Our results come with several surprises. Among these, we find that even using $k = 1 + o(1)$ request fragmentation, the optimal competitive ratio---which was $\Theta(\log M)$ in the classical setting---collapses to $\Theta(\log \log M)$. This result is shown to be tight with matching upper and lower bounds, applying to both deterministic and randomized algorithms.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-31 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.28462 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T11:23:11.262Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-31?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).