Abstrakt. Vi betraktar problemet med resurstilldelning i en parallell miljö där nya inkommande resurser anländer online i grupper eller omgångar. Vi studerar detta scenario i en abstrakt ram för att fördela bollar i soptunnor. Vi ser över tilldelningsalgoritmen GREEDY[2] på grund av Azar, Broder, Karlin och Upfal (SIAM J. Comput. 1999), där varje boll, för sekventiellt ankommande bollar, väljer två bins slumpmässigt, och placeras i en av dessa två bins med minsta belastning. Den maximala belastningen av en bin efter den sista bollen tilldelas av GREEDY[2] är väl förstådd, liksom faktiskt hela lastfördelningen, för ett brett utbud av inställningar. Huvudsyftet med vårt papper är att studera bollar och bins tilldelningsprocesser i en parallell miljö med bollar som anländer i omgångar. I vår modell, m bollar anländer i omgångar av storlek n varje (med n är också lika med antalet bins), och bollarna i varje sats ska fördelas bland bins samtidigt. I denna inställning anser vi att en algoritm som använder GREEDY [2] för alla bollar inom ett givet parti, svaren på dessa bollars belastning frågor är med avseende på bin laster i slutet av föregående sats, och inte på något sätt beror på beslut som tas av andra bollar från samma parti. Vårt huvudsakliga bidrag är en snäv analys av den nya processen att fördela bollar i partier: vi visar att efter fördelningen av ett antal partier, gapet mellan maximal och minimal belastning är O(log n) med stor sannolikhet, och är därför oberoende av antalet partier som används.
Berenbrink m.fl. REF studerar d-valsprocessen i ett scenario där m-kulor tilldelas n-behållare i satser av storlek n vardera.
Multiple-choice Balanced Allocation in (almost) Parallel
{'venue': 'APPROX-RANDOM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}