GENERALIZED FIRST-FIT ALGORITHMS IN TWO AND THREE DIMENSIONS

作     者：KEQIN LI KAM-HOI CHENG 

作者机构：Department of Computer Science University of Houston Houston Texas 77204–3475 USA Author’s current address is: Department of Mathematics and Computer Science State University of New York—the College at New Paltz New Paltz New York 12561 USA. 

出 版 物：《International Journal of Foundations of Computer Science》 

年 卷 期：1990年第1卷第2期

页      面：131-150页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Approximation algorithm asymptotic performance ratio First-Fit On-line packing Three dimensional bin packing Two dimensional bin packing 

摘      要：We investigate the two and three dimensional bin packing problems, i.e., packing a list of rectangles (boxes) into unit square (cube) bins so that the number of bins used is a minimum. A simple on-line packing algorithm for the one dimensional bin packing problem, the First-Fit algorithm, is generalized to two and three dimensions. We first give an algorithm for the two dimensional case and show that its asymptotic worse case performance ratio is . The algorithm is then generalized to the three dimensional case and its performance ratio . The second algorithm takes a parameter and we prove that by choosing the parameter properly, it has an asymptotic worst case performance bound which can be made as close as desired to 1.7 2 =2.89 and 1.7 3 =4.913 respectively in two and three dimensions.