装箱问题
箱子
计算机科学
上下界
包装问题
算法
数学优化
理论计算机科学
数学
数学分析
作者
E. G. Coffman,M. R. Garey,David S. Johnson
摘要
Motivated by potential applications to computer storage allocation, we generalize the classical one-dimensional bin packing model to include dynamic arrivals and departures of items over time. Within this setting, we prove close upper and lower bounds on the worst-case performance of the commonly used First Fit packing algorithm, and, using adversary-type arguments, we show that no on-line packing algorithm can satisfy a substantially better performance bound than that for First Fit.
科研通智能强力驱动
Strongly Powered by AbleSci AI