Bin Packing regarding Optimization and Decision Versions

Question

I'm studying for an exam and we were given a set of practice problems. Here's one I'm struggling with and I hope somebody can help shed some light on the right approach to this problem:

Here's my initial go at the problem:

Decision Version: To find the optimal solution using the decision version, I would try using various K's until I got a yes answer. Let's say the optimized solution is 7, I would try :

k=1, no
k=2, no
k=3, no
k=4, no
k=5, no
k=6, no
k=7, yes. 

So now that we know that the optimal solution is 7 bins, we solve the decision version by sorting the items by sizes from largest to smallest, and filling up the bins filling largest to smallest, and looping back over the bins until they are no more elements in the set.

If we have an optimal solution and we want to solve the decision version, I would take the number of bins returned by the optimal solution, and run it on the decision version to see if it returns yes.

I've never really seen a problem like this before so I'm not sure how the proper format is supposed to be.

Any help would be greatly appreciated!

Lori

Answer 1

There is a much better approach to solving the optimization problem based on the decision problem, note that your solution is exponential (pseudo-polynomial, but still exponential) in the size of the input, since if you have an algorithm that runs in T(n) on the decision problem, the suggested solution runs in O(k*T(n)), but since k is actually exponential in the size of the input (you need only log(k) bits to represent it), you have an exponential run time.

However, you can apply binary search on the problem, and require only O(log(k)) invokations of the algorithm of the decision problem in order to solve the optimization problem.

Now, if P=NP, and such algorithm (for solving the decision problem) exists in polynomial time O(p(n)), solving the optimization problem will be done in O(p(n) * log(k)) - which is polynomial in the size of the input.

The binary search will go something like that:

k <- 1
while decision_bin_packing(G,k) == false:
    k <- k * 2
perform binary search for the smallest value t in [k/2,k] such that decision_bin_packing(G,t)==true

The last binary search is pretty standard, and can be easily implemented with only O(logk) invokations of decision_bin_packing.

Danseur

Thanks for the response. How would I go about phrasing my binary search in the solution? So now I know that the solution has 7 bins, I would run a binary search on what list looking for what value? – Lori

@Lori See edit, tried to elaborate a bit about it. The actual implementation of binary search is fairly easy. – Danseur