# 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. Oct 3, 2015 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.