An O(n) bin-packing algorithm for uniformly distributed data |
| |
| Authors: | J. Csirik G. Galambos |
| |
| Affiliation: | 1. Department of Computer Science, József Attila University Szeged, Somogyi B. u. 7, H-6720, Szeged, Hungary
2. Lehrstuhl für Angewandte Mathematik II, Universit?t Augsburg, Memminger Strasse 6, D-8900, Augsburg, Germany
|
| |
| Abstract: | We give a first-fit type algorithm, with running timeO(n), for the classical one-dimensional bin-packing problem, and examine it from a probabilistic point of view. Our main result is that the expected waste for this algorithm isO(n 2/3). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
