4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do you have a conjecture? Do you think the case you're considering is the worst? $\endgroup$ – Yuval Filmus Jan 23 '14 at 1:25
  • $\begingroup$ You might want to ask it over at cstheory. Just make sure you rephrase it more clearly: you're trying to minimize the probability that all bins are at most 1, over all possible sizes of items adding up to $x$. $\endgroup$ – Yuval Filmus Jan 23 '14 at 1:27

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.