# How to distribute items of varying sizes into bins of varying sizes, such that percent utilization across all bins is minimized?

I have a bunch of databases, each having different access patterns, such that each puts a different amount of load on its database cluster. I would like to distribute them around my set of database clusters such that the workload for the clusters is evenly distributed.

I looked at the k-partition problem, which sounds close to what I want, except each of my database clusters has a different load capacity. That means I need an algorithm that minimizes what percent of load capacity is used on all clusters, whereas the k-partition problem minimizes the integer load on each cluster.

Does such an algorithm exist? And can anyone point me to a sample implementation of it?

-
In the special case that all center capacities are the same your problem is equivalent to k-partition, which is NP-hard (even when weights are polynomially bounded integers). In practice, you might solve the natural LP relaxation, then randomly round the solution. (E.g., Let variable $X_{ij}$ represent the fraction of database $i$ that the LP solution maps to cluster $j$. Choose a single random cluster $\hat j(i)$ to actually use for $i$ by drawing randomly from the distribution $p$ defined by $p_i = X_{ij}$. Maybe polish this solution with some local improvement. – Neal Young Nov 21 '12 at 17:03
Can you please clarify what a "natural LP relaxation" is? – spiffytech Nov 26 '12 at 14:30
If I understand you right, you mean, e.g., if cluster A has a capacity of 1x and cluster B has a capacity of 2x, Xij gives i a probability of 33% of mapping the database to cluster A, and 66% to cluster B, and I randomly choose from that distribution. Correct? – spiffytech Nov 26 '12 at 14:35
The LP relaxation is $\min\{ \lambda : (\forall i) \sum_{j} X_{ij} \ge 1; (\forall j) \sum_{i} L_{ij} X_{ij} \le \lambda C_{ij}; X \ge 0\}$. The variables are $\lambda$ and the $X_{ij}$'s, where $X_{ij}$ is the fraction of database $i$ mapped to cluster $j$. The constants are $L_{ij}$ (the load that database $i$ would put on cluster $j$ if mapped there), and $C_{ij}$ (the load capacity of cluster $j$). First, use an LP solver to solve this LP relaxation. Then, randomly round it by choosing, for each database $i$, a cluster $\hat j(i)$ as described in my other comment. – Neal Young Nov 26 '12 at 18:02
I suppose a greedy heuristic will give a fast and reasonably good solution most of the time. Do you need an optimal solution? – Paresh Dec 23 '12 at 23:12