Vi löser ett öppet problem i litteraturen genom att tillhandahålla en online-algoritm för multidimensionell bin packning som endast använder avgränsat utrymme. För att uppnå detta inför vi en ny teknik för att klassificera de föremål som ska packas. Vi visar att vår algoritm är optimal bland avgränsade rymdalgoritmer för alla dimensioner d > 1. Dess asymptotiska prestandaförhållande är (Π ∞ ) d, där Π ❌  och 1.691 är det asymptotiska prestandaförhållandet för den endimensionella algoritmen Harmonic. En modifierad version av denna algoritm för fallet där alla objekt är hyperkuber visas också vara optimal. Dess asymptotiska prestandaförhållande är sublinjärt i d. Dessutom utökar vi de tekniker som används i dessa algoritmer för att ge optimala algoritmer för online avgränsade utrymme variabel-storlek packning och resursförstärkt packning.
För ett stort antal aktiva bins presenterade Epstein och van Stee REF en (Π ❌ ) kompetitiv rymdbegränsad algoritm, där Π ❌  och 1.69103 är konkurrensförhållandet för den endimensionella algoritmen Harmonic.
Optimal Online Algorithms for Multidimensional Packing Problems ∗
{'venue': 'SIAM J. Discrete Math.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}