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

Question

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.

Answer 1

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.