2
$\begingroup$

In textbook by Vazirani's textbook, chapter 9 about Bin Packing. He give the following lemma.

Lemma 9.4 Let $\epsilon >1$ be fixed, and let K be a fixed nonnegative integer. Consider the restriction of the bin packing problem to instances in which each item is of size at least $\epsilon$ and the number of distinct item sizes is K. There is a polynomial time algorithm that optimally solves this restricted problem.

Proof. The number of items in a bin is bounded by $1/\epsilon$. Denote this by M. Therefore, the number of different bin types is bounded by $R = \binom{M+K}{M}$. Which is a large constant. Clearly, the total number of bins used is at most n. Therefore, the number of possible feasible packings is bouned by $P=\binom{n+R}{R}$, which is polynomial in n. Enumerating them and picking the best packing gives the optimal answer.

Question: We know a fact which is: $\binom{n+k-1}{n}$, now in order to find the number of different bin types we it should be something like $\binom{M+K-1}{M}$ why in the proof it is different?!!

$\endgroup$
  • $\begingroup$ 1) A binomial coefficient is not a fact. 2) Maybe the term for R is wrong, but as it's constant, the exact value does not matter for the proof as a whole. $\endgroup$ – Raphael Apr 15 '17 at 10:18
  • $\begingroup$ @Raphael No, it does matter, see the textbook and see exercise 9.4 $\endgroup$ – YOUSEFY Apr 15 '17 at 10:20
1
$\begingroup$

The bins contain at most $M$ elements rather than exactly $M$ elements. This is why your formula doesn't work. In order to use your formula, we need to allow for one more type of element, a dummy type, and then we get $\binom{M+(K+1)-1}{M} = \binom{M+K}{M}$.

As an example, suppose that there is one type of element (so $K=1$). In that case, a bin can contain $0,\ldots,M$ elements, in total $M+1 = \binom{M+K}{M}$ choices.

$\endgroup$
  • $\begingroup$ tricky point in the the proof I didn't notice, Thank you Yuval! $\endgroup$ – YOUSEFY Apr 15 '17 at 11:44

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.