3
$\begingroup$

I am taking an introductory course in complexity theory, and as an exercise, we were given the following problem.

Consider the bin packing problem, with objects of positive (rational) weights $W = \{w_1, w_2, ..., w_n\}$ ($0 < w_i \leq 1 \forall i$) that should be placed in bins of capacity 1. Imagine that you are given a "magical function" $\phi$ that, given a set $W$ of weights, gives you the minimum number $k$ of bins needed to pack the corresponding objects, i.e., $\phi(W) = k$. Let $T(n)$ denote the running time of the implementation of $\phi(W)$ and construct an algorithm that returns an optimal packing and runs in $O(f(n) + g(n)T(n))$ time, where $f(n)$ and $g(n)$ are polynomials.

First, I tried to recursively make binary partitions of $W$ by using that $\phi(W_1) + \phi(W_2) = \phi(W)$ for any partition $W_1 \cup W_2 = W$ such that $W_1$ and $W_2$ separates objects that are in different bins in an optimal solution (that is, there is an optimal solution such that no weights in $W_1$ share bins with any weight in $W_2$). When we eventually get $\phi(W_j) = 1$, we know that $W_j$ corresponds to the objects in bin $j$ in an optimal solution. However, my attempts here only yield algorithms with $g(n)$ being exponential in $n$.

Second, I tried to construct the bins one by one, using that, for all bins $B_j$, $\phi(B_j) + \phi(W \setminus B_j) = k$. Again, I have yet to find an algorithm where $g(n)$ is polynomial.

It's rather frustrating, as this seems to be a simple problem. Any suggestions on where I should begin?

$\endgroup$
  • $\begingroup$ Less elegant (and probably slower) than Yuval's answer, but you can find an optimal partition recursively. For all $i$, find an optimal partition of $W\setminus\{w_i\}$ using the $\phi$-oracle, and check whether you can add $w_i$ to one of the resulting bins such that the total number of bins is $\phi(W)$. $\endgroup$ – Ariel Apr 17 '18 at 15:51
2
$\begingroup$

Starting with $W$, repeatedly try to find two weights $w_i,w_j$ such that merging them (i.e., replacing both of them with $w_i+w_j$) doesn't increase the number of bins needed. Eventually, you will be left with $\phi(W)$ merged weights, which form a solution to the bin packing problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.