\(\newcommand{\footnotename}{footnote}\)
\(\def \LWRfootnote {1}\)
\(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\let \LWRorighspace \hspace \)
\(\renewcommand {\hspace }{\ifstar \LWRorighspace \LWRorighspace }\)
\(\newcommand {\mathnormal }[1]{{#1}}\)
\(\newcommand \ensuremath [1]{#1}\)
\(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \)
\(\newcommand {\setlength }[2]{}\)
\(\newcommand {\addtolength }[2]{}\)
\(\newcommand {\setcounter }[2]{}\)
\(\newcommand {\addtocounter }[2]{}\)
\(\newcommand {\arabic }[1]{}\)
\(\newcommand {\number }[1]{}\)
\(\newcommand {\noalign }[1]{\text {#1}\notag \\}\)
\(\newcommand {\cline }[1]{}\)
\(\newcommand {\directlua }[1]{\text {(directlua)}}\)
\(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\)
\(\newcommand {\protect }{}\)
\(\def \LWRabsorbnumber #1 {}\)
\(\def \LWRabsorbquotenumber "#1 {}\)
\(\newcommand {\LWRabsorboption }[1][]{}\)
\(\newcommand {\LWRabsorbtwooptions }[1][]{\LWRabsorboption }\)
\(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\)
\(\def \mathcode #1={\mathchar }\)
\(\let \delcode \mathcode \)
\(\let \delimiter \mathchar \)
\(\def \oe {\unicode {x0153}}\)
\(\def \OE {\unicode {x0152}}\)
\(\def \ae {\unicode {x00E6}}\)
\(\def \AE {\unicode {x00C6}}\)
\(\def \aa {\unicode {x00E5}}\)
\(\def \AA {\unicode {x00C5}}\)
\(\def \o {\unicode {x00F8}}\)
\(\def \O {\unicode {x00D8}}\)
\(\def \l {\unicode {x0142}}\)
\(\def \L {\unicode {x0141}}\)
\(\def \ss {\unicode {x00DF}}\)
\(\def \SS {\unicode {x1E9E}}\)
\(\def \dag {\unicode {x2020}}\)
\(\def \ddag {\unicode {x2021}}\)
\(\def \P {\unicode {x00B6}}\)
\(\def \copyright {\unicode {x00A9}}\)
\(\def \pounds {\unicode {x00A3}}\)
\(\let \LWRref \ref \)
\(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\)
\( \newcommand {\multicolumn }[3]{#3}\)
\(\require {textcomp}\)
\(\newcommand {\intertext }[1]{\text {#1}\notag \\}\)
\(\let \Hat \hat \)
\(\let \Check \check \)
\(\let \Tilde \tilde \)
\(\let \Acute \acute \)
\(\let \Grave \grave \)
\(\let \Dot \dot \)
\(\let \Ddot \ddot \)
\(\let \Breve \breve \)
\(\let \Bar \bar \)
\(\let \Vec \vec \)
\(\newcommand {\tcbset }[1]{}\)
\(\newcommand {\tcbsetforeverylayer }[1]{}\)
\(\newcommand {\tcbox }[2][]{\boxed {\text {#2}}}\)
\(\newcommand {\tcboxfit }[2][]{\boxed {#2}}\)
\(\newcommand {\tcblower }{}\)
\(\newcommand {\tcbline }{}\)
\(\newcommand {\tcbtitle }{}\)
\(\newcommand {\tcbsubtitle [2][]{\mathrm {#2}}}\)
\(\newcommand {\tcboxmath }[2][]{\boxed {#2}}\)
\(\newcommand {\tcbhighmath }[2][]{\boxed {#2}}\)
\(\newcommand {\Batched }{b\text {-}{\rm B{\small ATCHED}}}\)
\(\newcommand {\OneChoice }{{\rm O{\small NE}}\text {-}{\rm C{\small HOICE}}}\)
\(\newcommand {\TwoChoice }{{\rm T{\small WO}}\text {-}{\rm C{\small HOICE}}}\)
\(\newcommand {\DSample }{d\text {-}{\rm S{\small AMPLE}}}\)
\(\newcommand {\TwoSample }{{\rm T{\small WO}}\text {-}{\rm S{\small AMPLE}}}\)
\(\newcommand {\Graphical }{{\rm G{\small RAPHICAL}}}\)
\(\newcommand {\DChoice }{d\text {-}{\rm C{\small HOICE}}}\)
\(\newcommand {\GBounded }{g\text {-}{\rm B{\small OUNDED}}}\)
\(\newcommand {\GMyopic }{g\text {-}{\rm M{\small YOPIC}}}\)
\(\newcommand {\RelativeThreshold }{{\rm R{\small ELATIVE}\text {-}T{\small RHESHOLD}}}\)
\(\newcommand {\MeanThinning }{{\rm M{\small EAN}\text {-}T{\small HINNING}}}\)
\(\newcommand {\TwoThinning }{{\rm T{\small WO}\text {-}T{\small HINNING}}}\)
\(\newcommand {\DThinning }{d\text {-}{\rm T{\small HINNING}}}\)
\(\newcommand {\Twinning }{{\rm T{\small WINNING}}}\)
\(\newcommand {\Threshold }{{\rm T{\small HRESHOLD}}}\)
\(\newcommand {\Thinning }{{\rm T{\small HINNING}}}\)
\(\newcommand {\KThreshold }{k\text {-}{\rm T{\small HRESHOLD}}}\)
\(\newcommand {\OnePlusBeta }{(1+\beta )}\)
\(\newcommand {\Packing }{{\rm P{\small ACKING}}}\)
\(\newcommand {\Quantile }{{\rm Q{\small UANTILE}}}\)
\(\newcommand {\Memory }{{\rm M{\small EMORY}}}\)
\(\newcommand {\N }{\mathbb {N}}\)
\(\newcommand {\R }{\mathbb {R}}\)
\(\newcommand {\Oh }{\mathcal {O}}\)
\(\newcommand {\AdvTauDelay }{\tau \text {-}{\rm A{\small DV}}\text {-}{\rm D{\small ELAY}}}\)
\(\newcommand {\RandomTauDelay }{\tau \text {-}{\rm R{\small AND}}\text {-}{\rm D{\small ELAY}}}\)
\(\newcommand {\TauDelay }{\tau \text {-}{\rm D{\small ELAY}}}\)
\(\newcommand {\SigmaNoisyLoad }{\sigma \text {-}{\rm N{\small OISY}}\text {-}{\rm L{\small OAD}}}\)
\(\newcommand {\Heterogeneous }{{\rm H{\small ETEROGENEOUS}}}\)
\(\newcommand {\Gap }{\mathrm {Gap}}\)
\(\newcommand {\eps }{\epsilon }\)
The Packing Process
The \(\Packing \) process extends the idea of \(\Twinning \) and when sampling an underloaded bin (i.e., a bin \(i\) with \(x_i^t < t/n\)) it allocates to it as many balls as to make it (just) overloaded and when sampling an overloaded bin it allocates to it one ball.
The \(\Packing \) process:
Iteration: At each step \(t = 1, 2, \ldots \),
-
• Sample a bin \(i = i^t\) uniformly at random.
-
• Update its load:
\[ x_i^{t+1} = \begin {cases} \left \lceil \frac {W^t}{n} \right \rceil + 1 & \text {if }x_i^t < W^t/n \\ x_i^t + 1 & \text {if }x_i^t \geq W^t/n. \end {cases} \]
.