An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$).
The item are now randomly distributed into $2x$ bins (you may assume $2x\in \mathbb{N}$).
What's the probability (i.e. what can we guarantee to achieve for any adversarial choice) no bin contains items with total size > 1?
For example, if the adversary chose all items (except for the last one) to be of size $\frac{1}{2} + \epsilon$ , then we have $2x-1$ items that no two of them can fit in a single bin. The last item can fit everywhere. hence the probability is bounded by (relaxing to $2x-1$ bins):
$\frac{(2x-1)!}{(2x-1)^{2x-1}} < e^{-(2x-1)}$ .
On the other hand, all I know for a general item set is that a "good" coloring exist (easy to see using the first fit algorithm).
Any ideas?
