Suppose you have items, whose total size (i.e. sum of sizes) is $k$. The number of items and their individual sizes are unknown integers. We need to pack the items into bins of size $r$.

I need to find a number of bins $X$, such that given a random distribution of the items into bins (every item goes to every bin w.p. $1/X$), all bins will satisfy the size limit (i.e. no bin will contain items of size more than r) with as high as possible probability.

If, for a specific $X$, we denote the success probability by $P_X$, then my goal is to minimize $\frac{X + 1 \choose k + 1}{P_X}$ (for an adversarial selection of item number and sizes).

We have pretty much established that if $X < \frac{2k}{r+1}$, then $P_X=0$ (or $X < \frac{2k}{r}$, in case $r$ is even).

I believe that if we pick $X = \frac{2k}{r}$, then we get a probability bound of $P_X \geq X!/X^X > e^{-X}$, since it looks like the worst case is when all items are of size $(r/2 + \epsilon)$, where $\epsilon \in {0.5,1}$ depending on whether $r$ is odd or even.

If this is indeed the worst case, I have to get all of the items colored by different colors (packed into different random beans), so the bound $P_X \geq X!/X^X$ is tight.

The motivation for this problem comes from random coloring of graphs, where I want to color weighted vertices, such that no color will have vertices of weight more than $r$ colored by it.


A try to formalize the question in a simpler manner:

Find a minimal number of colors $C$, such that if we randomly color an item set $I$, whose total size is $k$:

The probability of the event where there is a color in which an items of size $> r$ is only exponentially low in $k$.

  • 3
    $\begingroup$ first this looks like homework, and second it does not look like a question (seems you answered it yourself) $\endgroup$ Dec 29 '13 at 15:37
  • $\begingroup$ I've answered the question for a specific value of r, not for the general case. This is not a homework, but rather a part of complexity analysis of some algorithm I'm working on. $\endgroup$
    – Ran B
    Dec 29 '13 at 15:57
  • 2
    $\begingroup$ This site is for research level questions, and I am afraid this is not such a question. You can try to ask at CS@SE. Unless I am missing something, it's very easy to show that the first fit algorithm achieves the bound. $\endgroup$ Dec 29 '13 at 16:08
  • 2
    $\begingroup$ @RanB If you want to revise a question, please use the edit link instead of posting a new question. I've copied your new version on top of this one but somebody will need to approve my edit before it's visible. $\endgroup$ Dec 30 '13 at 10:28
  • 1
    $\begingroup$ I would've preferred closing this question as off topic and leaving the other one. The two are actually quite different questions. $\endgroup$ Dec 30 '13 at 11:16

Your Answer

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

Browse other questions tagged or ask your own question.