Los, Dimitrios, Sauerwald, Thomas and Sylvester, John 
ORCID: 0000-0002-6543-2934
(2024)
The Power of Filling in Balanced Allocations.
SIAM Journal on Discrete Mathematics, 38 (1).
pp. 529-565.
|
Text
FillingNew.pdf - Author Accepted Manuscript Download (662kB) | Preview |
Abstract
We introduce a new class of balanced allocation processes which are primarily characterized by ``filling"" underloaded bins. A prototypical example is the Packing process: At each round we only take one bin sample, and if the load is below the average load, then we place as many balls until the average load is reached; otherwise, we place only one ball. We prove that for any process in this class the gap between the maximum and average load is \scrO(log n) w.h.p. for any number of balls m \geqslant 1. For the Packing process, we also provide a matching lower bound. Additionally, we prove that the Packing process is sample efficient in the sense that the expected number of balls allocated per sample is strictly greater than one. Finally, we also demonstrate that the upper bound of \scrO(log n) on the gap can be extended to the Memory process studied by Mitzenmacher, Prabhakar, and Shah [43rd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, BC, Canada, 2002, pp. 799-808].
| Item Type: | Article |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 31 Aug 2023 07:58 |
| Last Modified: | 10 Apr 2024 10:39 |
| DOI: | 10.1137/23m1552231 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3172433 |
Dimensions
Dimensions
