# To minimise max bin sizes in two-level balls-and-bin problem

Basically we consider two levels of mapping (the first is called partition and second mapping strategy) of balls into bins. And try to find the best partition strategy (the first level of mapping) to minimised the max bin sizes.

To state the problem precisely, it is a bit complex. Suppose there is a set of $m$ bins, partition number $k$ and $n$ balls. Balls are ordered with index $i$, $(1\leq i\leq n)$, and ball $i$ has weight $w_i$.

Firstly, the set of balls is partitioned into $k$ disjoint subset in their original order (here $m \leq n$ and $k \leq n$). For instance, if there are $n=6$ balls, with weights $3, 1, 3, 2, 2, 1$ and $k=4$, one way to do partition is $(3), (1, 3), (2), (2, 1)$.

Then, each partition is mapped to one of $m$ bins by certain mapping strategy $M$. Afterwards, each bin $j$ has some partitions and has total weight $bw_j$. Following previous example, assume $n=4$, one mapping strategy is to map each partition in $(3), (1,3), (2), (2,1)$ to a distinct bin, that is, $[(3)], [(1,3)], [(2)], [(2,1)]$. The maximal bin weight is $bw_2=3+1=4$.

Our problem is how to partition the set of balls so that the maximal bin weight (i.e., $max(bw_j)$) is minimised. Here, we suppose we are provided with the best possible mapping strategy $M$.

We follow previous example for better illustrating the problem. Now, if $k$ is changed to $5$, the partitioning we seek is $(3), (1), (3), (2), (2, 1)$. We consider all mapping strategy $M$ and the best mapping is $[(3)], [(1), (2)], [(3)], [(2, 1)]$, yielding max bin weight being just $3$. The problem is how to design an algorithm to find such partitioning, like $(3), (1), (3), (2), (2, 1)$.

-
In general this will be difficult to do optimally. If you let $m=2$ and $k=n$, you have an instance of the Partition problem which is known to be NP complete. – deinst Jul 13 '11 at 0:11
@deinst: As stated, though, the question asks only for a good algorithm for the first stage, which is trivial if $k=n$. If that’s really what’s wanted, the simplest interesting case would seem to be $k=m$, with trivial second stage. – Brian M. Scott Jul 13 '11 at 4:28

If $k\leq m$, the following recursive algorithm should be pretty efficient:

Let $W(i,j)=\sum_{r=i}^{j}w_r$, $M(i,j)=max_{r=i}^{j}(w_r)$ and $\mu(i,j,p)$ be the minimum possible maximum partition weight when partitioning $w_i, w_{i+1}, \dots, w_j$ into $p$ (contiguous) partitions. We want $\mu(1,n,k)$.

We then determine $\mu(i,j,p)$ as follows:

if $p=1$ : $\mu(i,j,p) = W(i,j)$

if $j-i=p-1$ : $\mu(i,j,p) = M(i,j)$

else :

let $s=\lceil{(i+j)/2}\rceil$, $p_l=\lceil{p/2}\rceil$, $l = \mu(i,s-1,p_l)$, $p_r=\lfloor{p/2}\rfloor$, $r =\mu(s,j,p_r)$, $\mu(i,j,p) = max(l,r)$

if $l<r$ :

while $l<r$ and $s-i>p_l$ :

let $s=s-1$, $l = \mu(i,s-1,p_l)$, $r =\mu(s,j,p_r)$, $\mu(i,j,p) = min(\mu(i,j,p), max(l,r))$

if $l>r$ :

while $l>r$ and $j-s\geq p_r$ :

let $s=s+1$, $l = \mu(i,s-1,p_l)$, $r =\mu(s,j,p_r)$, $\mu(i,j,p) = min(\mu(i,j,p), max(l,r))$

$W(i,j)$ and $M(i,j)$ can be calculated (and remembered) only as needed. When $\mu(i,j,p)$ is updated, the value of $s$ can be saved so that the partition can be recovered.

-

Before looking for an answer, I think the problem statement should be simplified. If I understood rightly, we are given $n$ (balls), $m$ (bins), and $k$ (partition number). From there, we want to get the "best" distribution of balls in the bins, so that the maximum weight among the bins is minimized. Additionally, the number $k$ restricts the possible distributions; but, actually, we have two cases: if $k \ge m$ we really have no restriction (just seek the best distribution, and then define the partitions from there), if $k<m$, we will have no more than $k$ bins occupied (because each partition subset must go inside one bin); but this is equivalent to having just $k$ bins to start with.

Then, just define $b=min(k,m)$ as the "effective" number of bins available, forget about the partition thing, and restate the problem: We have $n$ positive numbers $w_1, w_2 \cdots w_n$, with $n>b$. We want to partition them in $b$ subsets such that the maximum sum among each subset is minimized.

Do we agree on this? (Edited: we don't. See joriki's comment. I leave the answer because it might be useful to clarify the statement, and to illustrate a simple -failed- attempt).

If so, I guess this problem has been alread studied (and I'd bet it has not a simple solution). It looks equivalent to the Multiprocessor scheduling problem to me.

-
I think you overlooked this crucial condition: "Firstly, the set of balls is partitioned into $k$ disjoint subset in their original order". As I understand the question, this is what makes the two-step process necessary. – joriki Jul 12 '11 at 15:22
@joriki: you're right – leonbloy Jul 12 '11 at 15:29
agree with @joriki: the first level of mapping (partition) follows the original order. – Richard Jul 12 '11 at 15:31