A new proof for the first-fit decreasing bin-packing algorithm |
| |
Authors: | Brenda S Baker |
| |
Institution: | Bell Laboratories, Murray Hill, New Jersey 07974 USA |
| |
Abstract: | This paper provides a new proof of a classical result of bin-packing, namely the performance bound for the first-fit decreasing algorithm. In bin-packing, a list of real numbers in (0,1] is to be packed into a minimal number of bins, each of which holds a total of at most 1. The first-fit decreasing (FFD) algorithm packs each number in order of nonincreasing size into the first bin in which it fits. In his doctoral dissertation, D. S. Johnson (“Near-Optimal Bin Packing Algorithms,” Doctoral thesis, MIT, Cambridge, Mass., 1973) proved that for every list L, , where FFD(L) and OPT(L) denote the number of bins used by FFD and an optimal packing, respectively. Unfortunately, his proof required more than 100 pages! This paper contains a much shorter and simpler proof that . |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|