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?
Adversarial bin packing
combinatorics;probability theory;lower bounds;knapsack problems;packing