Computing the asymptotic worst-case of bin packing lower bounds
This paper addresses the issue of computing the asymptotic worst-case of lower bounds for the Bin Packing Problem. We introduce a general result that allows to bound the asymptotic worst-case performance of any lower bound for the problem and to derive for the first time the asymptotic worst-case of the well-known bound L3 by Martello and Toth. We also show that the general result allows to easily derive the asymptotic worst-case of several lower bounds proposed in the literature.
bin packing lower bounds packing asymptotic worst-case analysis