clong@topaz.rutgers.edu (Chris Long) (02/21/88)
I need help (i.e. an efficient algorithm or pointers to such) on the following problem: We have k bins of varying sizes. Bin(i) can only hold items of type type(i), and each type(i) is distinct. Each bin has a size associated with it, i.e. bin(i) can hold at most size(i) items of type type(i). Now we have a certain number of boxes we wish to pack into these bins with each box containing a given number of items of each type. Do algorithms exist which give good approximations to a perfectly packed set of bins? If we were given that a perfect packing exists, how effiecient could we be? An example: bin(1) can hold 3 items of type(1); bin(2) can hold 2 items of type(2). box(1) contains 2 type(1)'s, 1 type(2); box(2) contains 3 type(1)'s, 0 type(2)'s; box(3) contains 1 type(1)'s, 1 type(2). In this case box(1) and box(3) together yield a perfect packing. In my application, the number of bins is 20-30, and the number of boxes is 200-300; we also know a perfect packing exists. Comments? -- Chris Long Rutgers University RPO 1878 CN 5063 New Brunswick, NJ 08903 (201)-932-1160