# Balanced weight distribution in buckets, with different weight per bucket

Is this problem a know variant of the optimisation version of the bin packing problem? There is an approximating algorithm for it?

Let $A = \{a_1,a_2,...a_n\}$ be a set of items, $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Each $a_i$ has a weight, based on the bin it is placed on (the item $a_i$ when placed on bin $b_j$ has weight $W_{i,j}$). Let $T(b_j)$ represent the total weight of the bucket $b_j$, $T(b_j) = \sum_{c=1}^t W_{c,j}$, which is the sum of the weights of each $a_c$ placed in $b_j$.

What is the optimal way to distribute all the items $a_i$ into the buckets $b_j$, such that each bucket $b_j$ has the almost same $T(b_j)$?

This problem came up when I'm trying to distribute a load in a distributed system, with distributed memory, such that each computer has almost the same amount of work. However, in my problem, when an item $a_i$ is placed in a specific computer, some other items from another set, say $x_{d..t}$, aggregate the work load on that server. The matrix $W_{c,j}$ is the map of the aggregated weights, for all choices of $b_j$ for the item $a_i$.

• Please specify exactly the quantity you wish to optimize. Also, note that this generalizes PARTITION and so is NP-hard. – Yuval Filmus Oct 3 '15 at 16:19

This problem is known as Unrelated Parallel Machine Scheduling. Minimizing $max_j T(b_j)$ has a 2-approximation, by LP-relaxation and rounding.