New classes of fast lower bounds for bin packing problems

The bin packing problem is one of the classical NP-hard optimization proble ms. In this paper, we present a simple generic approach for obtaining new f ast lower bounds, based on dual feasible functions. Worst-case analysis as well as computational results show that one of our classes clearly outperfo rms the previous best "economical" lower bound for the bin packing problem by Martello and Toth. which can be understood as a special case. In particu lar, we prove an asymptotic worst-case performance of 3/4 for a bound that can be computed in linear time for items sorted by size. In addition, our a pproach provides a general framework for establishing new bounds.