Premium
Bin packing with discrete item sizes, part II: Tight bounds on First Fit
Author(s) -
Coffman E. G.,
Johnson D. S.,
Shor P. W.,
Weber R. R.
Publication year - 1997
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199701/03)10:1/2<69::aid-rsa4>3.0.co;2-v
Subject(s) - mathematics , combinatorics , bin packing problem , sequence (biology) , upper and lower bounds , bin , constant (computer programming) , discrete mathematics , space (punctuation) , algorithm , computer science , mathematical analysis , genetics , biology , programming language , operating system
Abstract In the bin packing problem, a list L of n items is to be packed into a sequence of unit capacity bins with the goal of minimizing the number of bins used. First Fit (FF) is one of the most natural on‐line algorithms for this problem, based on the simple rule that each successive item is packed into the first bin of the sequence that currently has room for it. We present an average‐case analysis of FF in the discrete uniform model: The item sizes are drawn independently and uniformly at random from the set {1/ k ,…,( k ‐ 1)/ k }, for some k > 1. Let W FF ( L ) denote the wasted space in the FF packing of L , i.e., the total space still available in the occupied bins. We prove that $E[W^{FF}(L)]=O(\sqrt{nk})$ , i.e., there exists a constant c > 0 such that $E[W^{FF}(L)] \leq c \sqrt{nk}$ for all n, k sufficiently large. By a complementary lower bound argument, we prove that this result is sharp, unless k is allowed to grow with n at a rate faster than n 1/3 in which case E [ W FF ( L )] = θ( n 2/3 ). Finally, we show that this last result carries over to the continuous uniform model, where item sizes are chosen uniformly from [0, 1]. The O ( n 2/3 ) upper bound for the continuous model is new and solves a problem posed a decade ago. The proofs of many of these results require extensions to the theory of stochastic planar matching. © 1997 John Wiley & Sons, Inc. Random Struct. Alg. , 10 , 69–101 (1997)