Thumbnail
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

   Open content in new tab
Source: ACM Digital Library