  Since the Bin Packing Problem (BPP) is one of the main NP-hard problems, a
lot of approximation algorithms have been suggested for it. It has been proven
that the best algorithm for BPP has the approximation ratio of 3/2 and the time
order of O(n), unless P=NP. In the current paper, a linear 3/2-approximation
algorithm is presented. The suggested algorithm not only has the best possible
theoretical factors, approximation ratio, space order, and time order, but also
outperforms the other approximation algorithms according to the experimental
results, therefore, we are able to draw the conclusion that the algorithms is
the best approximation algorithm which has been presented for the problem until
now. Key words: Approximation Algorithm, Bin Packing Problem, Approximation
Ratio, NP-hard.
