I det här dokumentet studerar vi 1-rymdsbegränsad flerdimensionell binpackning och hyperkubpackning. En sekvens av objekt anländer över tiden, varje objekt är en d-dimensionell hyperbox (i bin förpackning) eller hyperkub (i hyperkub förpackning), och längden på varje sida är inte mer än 1. Dessa föremål måste vara förpackade utan överlappning i d-dimensionella hyperkuber med enhetslängd på varje sida. I d-dimensionellt utrymme, två dimensioner i och j definiera ett utrymme P ij. När ett föremål anländer, måste vi packa det i en aktiv behållare omedelbart utan någon kunskap om de framtida objekt, och 90 • -rotation på något plan P ij är tillåtet. Målet är att minimera det totala antalet behållare som används för att packa alla dessa objekt i sekvensen. I den 1-rymdsbegränsade varianten finns det bara en aktiv behållare för förpackning av det aktuella objektet. Om den aktiva behållaren inte har tillräckligt med utrymme för att packa föremålet, måste den stängas och en ny aktiv behållare öppnas. För d-dimensionell bin förpackning, en online-algoritm med konkurrensförhållande 4 d ges. Dessutom anser vi att D-dimensionell hyperkubpackning, och ger en 2 d+1 -tävlingsalgoritm. Dessa två resultat är den första studien av 1-rymdsbegränsad multidimensionell binpackning och hyperkubpackning.
Det d-dimensionella fallet med 1-rymdsbegränsad hyperkubpackning diskuterades i REF, där en 2 d+1 -tävlingsalgoritm beskrevs.
Online Algorithms for 1-Space Bounded Multi Dimensional Bin Packing and Hypercube Packing
{'venue': None, 'journal': 'Journal of Combinatorial Optimization', 'mag_field_of_study': ['Mathematics', 'Computer Science']}