<p>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$.</p>

<p>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.</p>

<p>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).</p>

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

<p>I believe that if we pick $X = \frac{2k}{r}$, then we get a probability bound of $P_X \geq X!/X^X &gt; 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.</p>

<p>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.</p>

<p>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.</p>

<p>~~~~~~~~~~</p>

<p>A try to formalize the question in a simpler manner:</p>

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

<p>The probability of the event where there is a color in which an items of size $&gt; r$ is only exponentially low in $k$.</p>

CC BY-SA 3.0
2013-12-29T15:37:16.083Z
first this looks like homework, and second it does not look like a question (seems you answered it yourself)
Sasho Nikolov
CC BY-SA 3.0
2013-12-29T15:57:58.873Z
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.
Ran B
CC BY-SA 3.0
2013-12-29T16:08:49.270Z
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](http://cs.stackexchange.com). Unless I am missing something, it's very easy to show that the first fit algorithm achieves the bound.
Sasho Nikolov
CC BY-SA 3.0
2013-12-30T09:51:16.233Z
Thanks for your comments @SashoNikolov.

I've uploaded the full version of the problem I'm facing here:
http://cstheory.stackexchange.com/questions/20370/randomized-bin-packing-upper-bound-total-size-of-items-k-bin-size-r

Hope you'll find it a bit more challenging :).
Ran B
CC BY-SA 3.0
2013-12-30T10:28:07.037Z
@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.
David Richerby
CC BY-SA 3.0
2013-12-30T10:55:53.847Z
I've approved the edit, thanks for your help.
Ran B
CC BY-SA 3.0
2013-12-30T11:16:03.877Z
I would've preferred closing this question as off topic and leaving the other one. The two are actually quite different questions.
Sasho Nikolov
CC BY-SA 3.0
2013-12-31T08:24:49.210Z
Here is a simplified version of the question, which I believe should suffice:

Suppose that item set $I$ (sum(I) = k) was randomly colored by (exactly) 2k/(r+1) colors.

What's the best lower bound on the probability that the coloring succeeded (i.e. there's no color which colors items of size more than r)?

A trivial lower bound is 1/k! ,
since using First Fit it's possible to show that a valid coloring exists, and since the sizes are integers, $|I|\leq k$, hence the number of colorings is at most k!.

My conjuncture is that the probability is at least $e^{-O(k)}$, (or even $e^{(2k)/(r+1)}$).
Ran B
CC BY-SA 3.0
2013-12-31T08:30:09.357Z
The intuition behind the conjuncture is that seemingly, the worst possible $I$ is a set of $(2k)/(r+1)$ items of size $(r+1)/2$.

If this is indeed the worst case, then all we need is that all of the items in $I$ will be colored by different colors, which gives a probability of $(x!)/(x^x) < e^{-x}$ where $x=|I|=(2k)/(r+1)$.

However, it seems that given an arbitrary $I'$, showing that the probability of coloring $I'$ is lower than $I$ is not simple ( I couldn't find local transformations from $I'$ to $I$ that preserves the probability bound).
Ran B
CC BY-SA 3.0
2013-12-31T12:09:09.653Z
@RanB Your question should be self-contained and people should be able to understand it without trawling through the comments. Please decide on a question and ask it, instead of constantly moving the goalposts.
David Richerby
CC BY-SA 3.0
2013-12-31T12:37:09.537Z
@DavidRicherby - I'm trying to share a way of thinking that might lead to a solution. Do you think it's better if I edit it into the opening question? (or maybe open a new question and link it here?).

Thanks!
Ran B
<upper-bounds><packing><combinatorics>
Bin packing upper bound: total size of items = k, bin size = r
Ran B
# Bin packing upper bound: total size of items = k, bin size = r

(Asked by: username_0 on 2013-12-29)

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$.

**Tags:** upper-bounds, packing, combinatorics
> **Comments:**
> **username_1**: first this looks like homework, and second it does not look like a question (seems you answered it yourself)  
> **username_0**: 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.  
> **username_1**: 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](http://cs.stackexchange.com). Unless I am missing something, it's very easy to show that the first fit algorithm achieves the bound.  
> **username_0**: Thanks for your comments @SashoNikolov.  I've uploaded the full version of the problem I'm facing here: http://cstheory.stackexchange.com/questions/20370/randomized-bin-packing-upper-bound-total-size-of-items-k-bin-size-r  Hope you'll find it a bit more challenging :).  
> **username_2**: @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.  
> **username_0**: I've approved the edit, thanks for your help.  
> **username_1**: I would've preferred closing this question as off topic and leaving the other one. The two are actually quite different questions.  
> **username_0**: Here is a simplified version of the question, which I believe should suffice:  Suppose that item set $I$ (sum(I) = k) was randomly colored by (exactly) 2k/(r+1) colors.  What's the best lower bound on the probability that the coloring succeeded (i.e. there's no color which colors items of size more than r)?  A trivial lower bound is 1/k! , since using First Fit it's possible to show that a valid coloring exists, and since the sizes are integers, $|I|\leq k$, hence the number of colorings is at most k!.  My conjuncture is that the probability is at least $e^{-O(k)}$, (or even $e^{(2k)/(r+1)}$).  
> **username_0**: The intuition behind the conjuncture is that seemingly, the worst possible $I$ is a set of $(2k)/(r+1)$ items of size $(r+1)/2$.  If this is indeed the worst case, then all we need is that all of the items in $I$ will be colored by different colors, which gives a probability of $(x!)/(x^x) < e^{-x}$ where $x=|I|=(2k)/(r+1)$.  However, it seems that given an arbitrary $I'$, showing that the probability of coloring $I'$ is lower than $I$ is not simple ( I couldn't find local transformations from $I'$ to $I$ that preserves the probability bound).  
> **username_2**: @RanB Your question should be self-contained and people should be able to understand it without trawling through the comments. Please decide on a question and ask it, instead of constantly moving the goalposts.  
> **username_0**: @DavidRicherby - I'm trying to share a way of thinking that might lead to a solution. Do you think it's better if I edit it into the opening question? (or maybe open a new question and link it here?).  Thanks!  

---

## 0 answers

