time-complexitybin-packing

# If the BinPack problem were in P, how to get a packing that minimizes the number of bins in P?

I have the following definition of a BinPack problem:

The problem is to place a certain number of objects in a certain number of bins. The objects have different weights, each bin accepting a maximum load (all bins can accommodate the same load here). The associated BinPack property is formally defined as follows:

Input:

• n: number of objects
• x1, ..., xn: n integers, the weights of the objects
• c: bin capacity (integer)
• k: number of bins

Output:

• Yes, if there is a possible packing.
• No, otherwise.

The following definition of a decision problem associated with the BinPack problem is also provided: Let this problem be called BinPackOpt

Input:

• n: number of objects
• x1, ..., xn: n integers, the weights of the objects
• c: bin capacity (integer)
• k: number of bins

Output: A correct packing that minimizes number of bins.

I need to show that if the BinPack property was P, then BinPackOpt would also be P.

Therefore, I must construct a packing in polynomial time using the polynomial time algorithm of the BinPack problem. I already figured out how to get the minimum number of bins in polynomial time by using a binary search algorithm with bounds 1 and n initially and fixing the bounds according to outcome of the BinPack problem. That is, if we can accommodate the objects in "median" number of bins, then I fix the upper boundary to median, and if not, I fix the lower boundary to median + 1 which gives me an algorithm in O(P(n).log(n)) where P(n) is the complexity of the BinPack problem. However, I am not able to figure out how to get the actual packing of the objects in this optimal number of bins in polynomial time.

How can I solve this issue? Any help is appreciated.

Solution

• You can find the fewest number of bins necessary for `BinPackOpt` to find any packing, as you say, via a binary search in which `BinPack` will be called `O(log n)` times.

Let's say the minimum number of bins necessary for a packing to be possible is found to be k. Then the following pseudocode will give you the optimal packing:

``````let current_set = {obj_1, ..., obj_n}
loop1: let test_obj be the first object in current_set
loop2: for each obj_i in current_set not equal to test_obj
let test_set = current_set - {test_obj, obj_i}
add a new object to test_set that has the combined weight of test_obj and obj_i
call BinPack on test_set with k bins of the given capacity
if BinPack succeeds
record that test_obj and obj_i are binned together
let current_set = test_set
goto loop1
record that test_obj is binned alone
let test_obj = test_obj+1
goto loop2
``````

The inner loop of the above places one object into a bin of the optimal packing using `O(n)` calls to `BinPack` so you can find the whole optimal packing with `O(n^2)` calls to `BinPack`.