Skip to main content
edited title
Source Link

A balls into bins problem with combinatorial capacity constraints

We are given $m$ balls and $n$ bins, with $m \ge n$. Each bin has the same capacity integer value $c$, i.e. it can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into one bin selected independently and uniformly at random from the set of non-full bins remained (i.e. the ones containing less than $c$ balls).


Question: Given a positive integer $n'\le n$, what is the minimum number of balls that it is necessary to place into bins in such a way that the expected number of bins containing at least $\frac{c}{2}$ balls is equal to at least $n'$?

(What about the minimum number of balls for having that the expected number of full bins is equal to at least $n'$?)

A balls into bins problem with combinatorial capacity constraints

We are given $m$ balls and $n$ bins, with $m \ge n$. Each bin has the same capacity integer value $c$, i.e. it can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into one bin selected independently and uniformly at random from the set of non-full bins remained (i.e. the ones containing less than $c$ balls).


Question: Given a positive integer $n'\le n$, what is the minimum number of balls that it is necessary to place into bins in such a way that the expected number of bins containing at least $\frac{c}{2}$ balls is equal to at least $n'$?

(What about the minimum number of balls for having that the expected number of full bins is equal to at least $n'$?)

A balls into bins problem with combinatorial constraints

We are given $m$ balls and $n$ bins, with $m \ge n$. Each bin can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into one bin selected independently and uniformly at random from the set of non-full bins remained (i.e. the ones containing less than $c$ balls).


Question: Given a positive integer $n'\le n$, what is the minimum number of balls that it is necessary to place into bins in such a way that the expected number of bins containing at least $\frac{c}{2}$ balls is equal to at least $n'$?

(What about the minimum number of balls for having that the expected number of full bins is equal to at least $n'$?)

edited body
Source Link

We are given $m$ balls and $n$ bins, with $m \gg n$$m \ge n$. Each bin has the same capacity integer value $c$, i.e. it can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into one bin selected independently and uniformly at random from the set of non-full bins remained (i.e. the ones containing less than $c$ balls).


Question: Given a positive integer $n'\le n$, what is the minimum number of balls that it is necessary to place into bins in such a way that the expected number of bins containing at least $\frac{c}{2}$ balls is equal to at least $n'$?

(What about the minimum number of balls for having that the expected number of full bins is equal to at least $n'$?)

We are given $m$ balls and $n$ bins, with $m \gg n$. Each bin has the same capacity integer value $c$, i.e. it can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into one bin selected independently and uniformly at random from the set of non-full bins remained (i.e. the ones containing less than $c$ balls).


Question: Given a positive integer $n'\le n$, what is the minimum number of balls that it is necessary to place into bins in such a way that the expected number of bins containing at least $\frac{c}{2}$ balls is equal to at least $n'$?

(What about the minimum number of balls for having that the expected number of full bins is equal to at least $n'$?)

We are given $m$ balls and $n$ bins, with $m \ge n$. Each bin has the same capacity integer value $c$, i.e. it can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into one bin selected independently and uniformly at random from the set of non-full bins remained (i.e. the ones containing less than $c$ balls).


Question: Given a positive integer $n'\le n$, what is the minimum number of balls that it is necessary to place into bins in such a way that the expected number of bins containing at least $\frac{c}{2}$ balls is equal to at least $n'$?

(What about the minimum number of balls for having that the expected number of full bins is equal to at least $n'$?)

added 6 characters in body
Source Link

We are given $m$ balls and $n$ bins, with $m \gg n$. Each bin has the same capacity integer value $c$, i.e. it can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into one bin selected independently and uniformly at random from the set of non-full bins remained (i.e. the ones containing less than $c$ balls).


Question: Given ana positive integer $n'\in [n]$$n'\le n$, what is the minimum number of balls that it is necessary to place into bins in such a way that the expected number of bins containing at least $\frac{c}{2}$ balls is equal to at least $n'$?

(What about the minimum number of balls for having that the expected number of full bins is equal to at least $n'$?)

We are given $m$ balls and $n$ bins, with $m \gg n$. Each bin has the same capacity integer value $c$, i.e. it can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into one bin selected independently and uniformly at random from the set of non-full bins remained (i.e. the ones containing less than $c$ balls).


Question: Given an integer $n'\in [n]$, what is the minimum number of balls that it is necessary to place into bins in such a way that the expected number of bins containing at least $\frac{c}{2}$ balls is equal to at least $n'$?

(What about the minimum number of balls for having that the expected number of full bins is equal to at least $n'$?)

We are given $m$ balls and $n$ bins, with $m \gg n$. Each bin has the same capacity integer value $c$, i.e. it can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into one bin selected independently and uniformly at random from the set of non-full bins remained (i.e. the ones containing less than $c$ balls).


Question: Given a positive integer $n'\le n$, what is the minimum number of balls that it is necessary to place into bins in such a way that the expected number of bins containing at least $\frac{c}{2}$ balls is equal to at least $n'$?

(What about the minimum number of balls for having that the expected number of full bins is equal to at least $n'$?)

deleted 2 characters in body
Source Link
Loading
deleted 1 character in body
Source Link
Loading
added 4 characters in body
Source Link
Loading
added 134 characters in body
Source Link
Loading
deleted 19 characters in body; added 3 characters in body
Source Link
Loading
added 19 characters in body
Source Link
Loading
added 11 characters in body
Source Link
Loading
Source Link
Loading