IBM - Personal communication

This web page contains the abstract of my paper:

"A Counterexample to a Bin Packing Conjecture", SIAM J. Alg. and Disc. Meth., 2(1981), p. 309-310.

Abstract: In this paper we exhibit a counterexample to the following conjecture of Garey, Graham and Johnson: If L={a1,...,an} is an ordered list of items with sizes s(ai) (0<s(ai)<=1) let FF(L) be the number of bins of size 1 required by the "first-fit" algorithm to pack L. Let R(alpha)=lim sup (n goes to infinity) [(1/N)*max{FF(L)|L can be packed into N bins of size alpha}]. Let w(alpha)=max{sum i=1 to k of [1/(Pi-1)] | 2<=P1<=P2<=...; sum i=1 to k of [1/Pi] = alpha, the Pi are integers at least 2 of which are not equal to 2}. Then R(alpha)=w(alpha).

[ IBM Research home page | James B. Shearer's home page | Up ]
[ IBM home page | Order | Search | Contact IBM | Help | (C) | (TM) ]