Efficient Algorithms For Bin-Packing: Converting Np Complexity Into P Solutions
Anil Shankar Rao
Research Scholar, Department of Studies in Computer Science, Manasa Gangotri, University of Mysore, Mysore, Karnataka, India
Abstract
The main objective of this problem is to pack objects of fixed volume into bins, each of them having a maximum capacity, so as to minimize the total number of bins used. Bin packing is an Np-complete problem as the number items increases, to pack the items in n bins, it cannot be done in polynomial time. Hence we convert the Np problem to P problem in our approach. There are several methods to solve this problem. The most straightforward solution would be the first fit algorithm. Here each object is compared against all the bins to try find the first bin which could accommodate the object. Insert a set of n numbers into as few bins as possible, such that the sum of the numbers assigned to each bin does not exceed the bin capacity, we firstly prove it to be NP problem and solve as P problem after transformation