
arXiv: 2204.04057
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, 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 O( log n ) w.h.p. for any number of balls m ⩾ 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 O( log n) on the gap can be extended to the Memory process studied by Mitzenmacher, Prabhakar and Shah (2002).
FOS: Computer and information sciences, two-choices, Discrete Mathematics (cs.DM), maximum load, gap bounds, G.3, heavily loaded, G.2.m, memory, 4613 Theory Of Computation, 46 Information and Computing Sciences, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, 68W20, 68W27, 68W40, 60C05, Online algorithms; streaming algorithms, Analysis of algorithms, Data Structures and Algorithms (cs.DS), weighted balls, Combinatorial probability, Randomized algorithms, Probability (math.PR), 4901 Applied Mathematics, 4904 Pure Mathematics, G.3; G.2.m; F.2.2, 49 Mathematical Sciences, balls-into-bins, Combinatorics (math.CO), F.2.2, potential functions, balanced allocations, Mathematics - Probability, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, two-choices, Discrete Mathematics (cs.DM), maximum load, gap bounds, G.3, heavily loaded, G.2.m, memory, 4613 Theory Of Computation, 46 Information and Computing Sciences, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, 68W20, 68W27, 68W40, 60C05, Online algorithms; streaming algorithms, Analysis of algorithms, Data Structures and Algorithms (cs.DS), weighted balls, Combinatorial probability, Randomized algorithms, Probability (math.PR), 4901 Applied Mathematics, 4904 Pure Mathematics, G.3; G.2.m; F.2.2, 49 Mathematical Sciences, balls-into-bins, Combinatorics (math.CO), F.2.2, potential functions, balanced allocations, Mathematics - Probability, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
