Choice-memory tradeoff in allocations (Q990388)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5776894
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Choice-memory tradeoff in allocations |
scientific article; zbMATH DE number 5776894 |
Statements
Choice-memory tradeoff in allocations (English)
0 references
1 September 2010
0 references
The paper focuses on the balls-and-bins paradigm which describes the process where \(b\) balls are placed independently and uniformly at random in \(n\) bins. The authors study the above models in the presence of constraint on the memory that the online algorithm has at its disposal. They find that a tradeoff between the choice and the memory governs the ability to achieve a perfect allocation as well as a constant maximal load.
0 references
space/performance tradeoffs
0 references
balls and bins paradigm
0 references
0 references
0.8993596
0 references
0.89179814
0 references
0.8551704
0 references
0.8484129
0 references
0.8428394
0 references
0.8428394
0 references
