Motiverad av problemet med att packa virtuella maskiner på fysiska servrar i molnet, studerar vi problemet med endimensionell online stokastisk bin förpackning. Poster med storlekar som provtas oberoende och identiskt (i.i.d.) från en distribution med integral stöd anländer som en ström och måste packas vid ankomst i lådor av storlek B, också ett heltal. Storleken på en vara är känd när den anländer och målet är att minimera antalet icke-tomma behållare (eller motsvarande, avfall, definieras som det totala oanvända utrymmet i icke-tomma behållare). Online stokastisk bin packning har studerats ingående i teoretisk datavetenskap, kombinatorik och sannolikhetslitteratur, och det finns många heuristiker. Alla sådana heuristiker är dock antingen optimala för endast vissa klasser av artikelstorlekar, eller förlitar sig på att lära distributionen. Den state-of-the-art Summan av Squares heuristic (Csirik et al. [8]) erhålls sublinjärt (i antal sedda föremål) avfall för distribution där det förväntade avfallet för den optimala offlinealgoritmen är sublinjärt, men har en konstant faktor större avfall för distribution med linjärt avfall under OPT. I [8], författarna löste detta problem genom att lära distributionen och lösa en LP för att injicera fantom jobb i ankomstströmmen. Som vårt första bidrag presenterar vi två distributionsagnostiska bin packning heuristics som uppnår additivt O ( ε n) avfall jämfört med OPT för alla distributioner. Våra algoritmer är i huvudsak lutning nedstigning på lämpligt definierade Lagrangian avkopplingar av bin packa Linear Program. Den första algoritmen är mycket lik SS algoritmen, men konceptuellt packar bins top-down istället för bottom-up. Detta motiverar vår andra heuristiska som använder en annan Lagrangian avkoppling för att packa soptunnor bottom-up. Våra heuristiker kan också tolkas som iterativa Primal-Dual algoritmer, och ge en enhetlig bild av Primal-Dual algoritmer i stokastiska processer, konvex optimering och teoretiska datorvetenskapliga samhällen. Därefter anser vi att det mer allmänna problemet med online stokastisk bin förpackning med objekt avgångar där tidsåtgången för ett objekt endast avslöjas när objektet avgår. Våra algoritmer sträcker sig som till fallet med objekt avgångar, och vi visar deras utmärkta prestanda experimentellt. Vi ser också kort tillbaka på Best Fit heuristic som inte har studerats i scenariot med objekt avgångar ännu.
Helt nyligen har REF fått nya resultat på den klassiska endimensionella papperskorgen; den innehåller även heuristik och simuleringar för motsvarande system med objektavgångar, vilket är ett specialfall av vår modell.
Online Stochastic Bin Packing
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}