Det är väl känt att om n bollar sätts in i n bins, med hög sannolikhet, bin med maximal belastning innehåller (1 + o(1)) log n/ log log n bollar. Azar, Broder, Karlin och Upfal [1] visade att i stället för att välja en bin, om d ≥ 2 bins väljs slumpmässigt och bollen infogas i de minst laddade d bins, den maximala belastningen minskar drastiskt för att logga n/ log d + O(1). I detta papper studerar vi de två val bollar och bins process när bollar inte får välja två slumpmässiga bins, men bara bins som är anslutna med en kant i en underliggande graf. Vi visar att för n bollar och n bins, om grafen är nästan regelbunden med grad n, Där är inte för liten, de tidigare gränserna på den maximala belastningen fortsätter att hålla. Exakt är den maximala belastningen log n+O(1/ )+O(1). Så även om grafen har grad n (1/ log log n), är den maximala belastningen O(log log n). För allmänna grafer visar vi att den maximala belastningen är log log n+O( log n log( ska/ log 4 n) )+O(1) och även ger en nästan matchande lägre gräns för log log n+ log n log( ska logga n). Detta gäller inte heller för icke-regelbundna grafer även om minimigraden är hög. Vöcking [29] visade att den maximala binstorleken med d val belastningsbalansering kan förbättras ytterligare till O(log log n/d) genom att bryta band till vänster. Detta kräver d slumpmässiga bin val. Vi visar att sådana gränser kan uppnås genom att endast göra två slumpmässiga åtkomster och fråga d/2 sammanhängande fack i varje åtkomst. Genom att gruppera en sekvens av n bins i 2n/d grupper, var och en av d/2 på varandra följande bins, om varje boll väljer två grupper slumpmässigt och sätter in den nya bollen i den minst laddade bin i den mindre laddade gruppen, då den maximala belastningen är O(loggloggen n/d) med hög sannolikhet. Dessutom visar det sig också att denna uppdelning i grupper av storlek d/2 också är viktigt för att uppnå denna gräns, det vill säga, i stället för att välja två anpassade grupper, om vi helt enkelt väljer slumpmässiga men möjligen ojusterade slumpmässiga uppsättningar av d/2 på varandra följande bins, då den maximala belastningen hoppar till
Ett annat relaterat arbete i bollar och bins inställning är papper Kenthapadi och Panigrahy REF, som överväger en inställning där bollar inte får välja två bins, men tvingas välja två bins som motsvarar en kant på en underliggande slumpmässig graf.
Balanced allocation on graphs
{'venue': "SODA '06", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}