Vi förbättrar den nedre gränsen på den asymptotiska konkurrensförhållandet för någon online-algoritm för bin förpackning till över 1.54278. Vi demonstrerar för första gången fördelen med förgrening och tillämpligheten av full anpassningsförmåga i utformningen av lägre gränser för den klassiska online bin förpackning problem. Vi tillämpar en ny metod för viktbaserad analys, som vanligtvis endast används i bevis på övre gränser. Värdena för tidigare lägre gränser var cirka 1.5401 och 1.5403.
Bologh m.fl. REF förbättrade den nedre gränsen till 1.54278.
A new lower bound for classic online bin packing
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}