\(\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 }\)
Kenthapadi and Panigrahy (2006) studied the \(\TwoChoice \) process in the \(\Graphical \) setting where for each ball we sample one edge
uniformly at random and then allocate to the least loaded of the two endpoints. They proved that in dense graphs \(\Gap (m) = \Theta (\log \log n)\). This was extended by Peres, Talwar and Wieder (2015) to expanders with conductance \(\phi \) proving that \(\Gap (m) = \Oh (\frac {\log n}{\phi })\) for any \(m \geq n\). In [3], it was shown that the same bound holds even in the presence of weights and batches. Sublogarithmic bounds were proven in [4] for dense
expanders.
Below we define the \(\Graphical \) setting for any \(\TwoSample \) process.
\(\Graphical (\mathcal {P}, G)\)
Parameter:
-
• \(G = (V, E)\): An undirected connected graph.
-
• \(\mathcal {P}\): A \(\TwoSample (Q^t)\) process with decision function \(Q^t\).
Iteration: At step \(t \geq 0\), allocate ball \(t+1\) using
\(\seteqnumber{0}{}{0}\)
\begin{align*}
q_i^t(\mathfrak {F}^t) & = \sum _{(j_1, j_2) \in E} \sum _{k \in [2] : j_k = i} Q^t(\mathfrak {F}^t, j_1, j_2, k) \cdot \frac {1}{|E|}.
\end{align*}
Bansal and Feldheim (2022) analysed adaptive algorithms based on flow decompositions for proving \(\Oh (\mathrm
{polylog}(n))\) gap bounds. In [5], it was shown that the \(\Twinning \) and \(\Packing \) processes have an \(\Theta (\log n)\) gap for any \(d\)-regular graph (including
the cycle).
References
-
[1] Nikhil Bansal and Ohad N. Feldheim. “The power of two choices in graphical allocation”. In: 54th Annual ACM Symposium on Theory of Computing (STOC’22). Ed. by Stefano Leonardi and Anupam Gupta. New York,
NY, USA: ACM, 2022, pp. 52–63. doi: 10.1145/3519935.3519995. url: https://doi.org/10.1145/3519935.3519995.
-
[2] Krishnaram Kenthapadi and Rina Panigrahy. “Balanced allocation on graphs”. In: 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’06). ACM, New York, 2006, pp. 434–443. doi: 10.1145/1109557.1109606. url: https://doi.org/10.1145/1109557.1109606.
-
[3] Dimitrios Los and Thomas Sauerwald. “Balanced Allocations in Batches: Simplified and Generalized”. In: 34th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’22). Philadelphia, PA, USA:
ACM, 2022, 389–399. isbn: 9781450391467. doi: 10.1145/3490148.3538593. url: https://doi.org/10.1145/3490148.3538593.
-
[4] Dimitrios Los and Thomas Sauerwald. “Balanced Allocations with Incomplete Information: The Power of Two Queries”. In: 13th Innovations in Theoretical Computer Science Conference (ITCS’22). Vol. 215.
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 103:1–103:23. isbn: 978-3-95977-217-4. doi: 10.4230/LIPIcs.ITCS.2022.103. url: https://drops.dagstuhl.de/opus/volltexte/2022/15699.
-
[5] Dimitrios Los, Thomas Sauerwald, and John Sylvester. “Balanced Allocations: Caching and Packing, Twinning and Thinning”. In: 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’22). SIAM, 2022,
pp. 1847–1874. doi: 10.1137/1.9781611977073.74.
-
[6] Yuval Peres, Kunal Talwar, and Udi Wieder. “Graphical balanced allocations and the (1 + β)-choice process”. In: Random Structures & Algorithms 47.4 (2015), pp. 760–775. issn:
1042-9832. doi: 10.1002/rsa.20558. url: https://doi.org/10.1002/rsa.20558.