### New Algorithms for Bin PackingNew Algorithms for Bin Packing

Access Restriction
Subscribed

 Author Yao, Andrew Chi-Chih Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1980 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract In the bin-packing problem a list $\textit{L}$ of $\textit{n}$ numbers are to be packed into unit-capacity bins. For any algorithm $\textit{S},$ let $\textit{r}(\textit{S})$ be the maximum ratio $\textit{S}(\textit{L})/\textit{L}*$ for large $\textit{L}*,$ where $\textit{S}(\textit{L})$ denotes the number of bins used by $\textit{S}$ and $\textit{L}*$ denotes the minimum number needed. An on-line $\textit{&Ogr;}(\textit{n}$ log $\textit{n})-time$ algorithm RFF with $\textit{r}(RFF)$ = 5/3 and an off-line polynomial-time algorithm RFFD with $\textit{r}(RFFD)$ ≤ 11/9 - ε for some fixed ε > 0, are given. These are strictly better, respectively, than two prominent algorithms: the First-Fit (FF), which is on-line with $\textit{r}(FF)$ = 17/10, and the First-Fit-Decreasing (FFD) with $\textit{r}(FFD)$ = 11/9. Furthermore, it is shown that any on-line algorithm $\textit{S}$ must have $\textit{r}(\textit{S})$ ≥ 3/2. The question, “How well can an $\textit{&ogr;}(\textit{n}$ log $\textit{n})-time$ algorithm perform?” is also discussed. It is shown that in the generalized $\textit{d}-dimensional$ bin packing, any $\textit{&ogr;}(\textit{n}$ log $\textit{n})-time$ algorithm $\textit{S}$ must have $\textit{r}(\textit{S})$ ≥ $\textit{d}.$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1980-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 27 Issue Number 2 Page Count 21 Starting Page 207 Ending Page 227

#### Open content in new tab

Source: ACM Digital Library