Heuristic evaluation techniques for bin packing approximation algorithms

Performance analysis of approximation algorithms purposes to give upper bounds on the ratio «approximate solution cost»/«optimal solution cost». We say that standard analysis brings to «a priori» evaluation since the bounds it provides refer to the overall worst-case performance: really those evaluations do not take into account useful information relevant to the performance that approximate solution might contain themselves. In this paper we show how the performances of the Any Fit Decreasing algorithms for Bin Packing can be evaluated more precisely than it is done in the standard «a priori» analysis, by means of demonstration techniques of «a posteriori» analysis. In fact, we show how approximate solutions of Bin Packing given by Any Fit Decreasing algorithms can be put in three classes of performances. Belongings to the first class imply really optimality of solutions (those events could remain unspected if one clings only to the 5/4 bound, as forecast by standard «a priori» evaluations). Also belonging to the second class of performances may involve remarkable revaluation of solutions in hand, although optimality cannot be recognized; an inequality is provided which permits to compute upper bounds on the evaluation ratios. The same inequality permits to recognize approximate solutions which could not be improved neither by First Fit nor Best Fit Decreasing algorithms. The third class refers to those performances for which the considered levels of inspection cannot offer a more precise evaluation that the «a priori» one. © 1985, Instituto di Elaborazione della Informazione del CNR. All rights reserved.