2
$\begingroup$

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$.

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

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

$\endgroup$
  • $\begingroup$ The UPMS is what I described, and the GENERALIZED ASSIGNMENT is what I really need. Very helpful. Nice material also. $\endgroup$ – Thiago Borges Oct 3 '15 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.