Bin packing, Decision vs Optimization

Question

For an assignment I have been given the bin packing problem and asked to show how you can solve the decision version of the problem from the optimization version and vice versa. I understand that to solve the decision version you simply take the number of bins used in the optimization version and compare it to the max number of bins specified but how can I use the decision version to solve the optimization version?

Answer 1

You can use the decision version to solve the optimization version by observing that if N bins is sufficient, then K > N bins will also be sufficient.

Start with a single bin, and run the decision version on it. If the answer is true, you are done; otherwise, keep doubling the number of bins until you hit a true. Let's say that you get an answer of true when you try N = 2 ^ k. Then you can run a binary search between M = 2^(k-1) and N, inclusive, to find the exact solution to the optimization problem (both N and k come from the previous step).

Consider this example: let's say the optimal solution is 14. You could then try the following sequence of decision problem to find the answer:

• 1 --> false
• 2 --> false (doubled 1)
• 4 --> false (doubled 2)
• 8 --> false (doubled 4)
• 16 --> true (doubled 8; we've got a true, so proceed to the binary search)
• 12 --> false (midpoint between 8 and 16)
• 14 --> true (midpoint between 12 and 16)
• 13 --> false (midpoint between 12 and 14)

In general, the answer can be found in logarithmic time (i.e. in Log₂(Answer)).

Once you know the number of bins N required to package X objects, run a bipartite matching algorithm between the items on one side and the N bins on the other side. Assuming that the decision problem is solved correctly, such bipartite matching must exist, and can be found in polynomial time.