2
$\begingroup$

We are given an array of weights $W$ (all weights are positive integers), and we need to put the weights inside bins. Each bin can hold a maximum of Max_val, and each weight is at most Max_val. The variation is that the ordering of weights should not be changed, that is, $W_i$ should be inside a bin before $W_j$ is inserted, for all $i < j$.

For this problem statement, intuitively we can see that a greedy approach of filling a bin till its maximum value is reached and creating a new bin for further weights will produce the minimum number of bins. I am unable to come up with a formal proof that the greedy solution is optimal. Any hints or guidelines would be great!

$\endgroup$
2
$\begingroup$

Let $G$ be the solution produced by the greedy algorithm. For each other solution $S$, let $i(S)$ be the index of the first weight at which $S$ diverges from $G$. Let $O$ be an optimal solution maximizing $i(O)$. Thus $G$ places $i(O)$ in bin $j$ (for some $j$), and $O$ places $i(O)$ in bin $j+1$. If we move $i(O)$ to bin $j$ (which is possible since $O$ is ordered), we obtain a solution $O'$ using at most as many bins as $O$, and satisfying $i(O') > i(O)$. This contradicts the choice of $O$.

If we try to run this argument on the unrestricted bin packing algorithm, we will have trouble when moving $i(O)$ to bin $j$, since that bin might be occupied with other elements, not leaving enough room for $i(O)$. In the variant you consider, this cannot happen.

$\endgroup$
7
  • $\begingroup$ Why do we need O to be optimal solution maximizing i(O), why not just optimal solution? Thanks! $\endgroup$ May 1 '20 at 22:52
  • $\begingroup$ This is how my proof works. You’re welcome to come up with another. $\endgroup$ May 1 '20 at 22:54
  • $\begingroup$ Sorry now I understood, we need that for the final contradiction. But is it ok to assume the existence of an optimal solution that maximizes i(O). $\endgroup$ May 1 '20 at 23:00
  • $\begingroup$ Since there are only finitely many options for $i(O)$, I don’t see any problems. $\endgroup$ May 1 '20 at 23:01
  • $\begingroup$ I have recently only started to learn about proofs and proof techniques, So I am unable to grasp why finitely many options for i(O) implies the existence of an optimal solution that maximizes i(O). If there are any pre-requisites that I need to know tell me, it will be really helpful in my learning process. Thanks! $\endgroup$ May 1 '20 at 23:12

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.