Comparison of some bin packing heuristics

Abstract

One of the most interesting subjects in the area of algorithms is a class of problems called the "NP-complete" problems. The status of NP-complete problems is still unknown. If any of the NP-complete problems can be solved in polynomial time, every NP-complete problem can be solved in polynomial time. A number of NP-complete problems have been studied with no result leading to a polynomial time optimal solution. One of the approaches to finding a near optimal solution to an NP-complete problem is that of approximation algorithms. An approximation algorithm, often called "heuristic" algorithm, focuses on finding a "good" (not necessary optimal) solution to the problem in an acceptable amount of time. Some of the measures of performance of an approximation algorithm involve worst case and average case analyses. A well known problem in the field of approximation algorithms is a bin packing problem : given a list of sizes in the range (0,1] and an unlimited number of bins of size 1, find an assignment of sizes to bins, such that the sizes assigned to each bin have sum no greater than I and the number of bins used is minimized. The bin packing problem is an NP-complete problem; therefore there probably is no polynomial time algorithm for solving it. There are however several approximation algorithms used to solve the bin packing problem. The least researched class of algorithms for solving the bin packing problem is that of Best k Fit algorithms (BkF). The focus of this research is the Best 3 Fit algorithm. Here the worst case behavior has been studied, and an upper bound developed. A statistical analysis of the average case behavior has been performed; and the results are discussed and compared to the behavior of previously developed approximation algorithms. The Best 3 Fit algorithm performs worse in the worst case than some of the discussed algorithms. On the average, however, it performs better than the other algorithms.