0
$\begingroup$

I'm trying to find reading material on a particular problem I'm interested in, but I don't know the terms to search.

Problem assumptions/definitions:

  • We have finite number of items I with weights [0, 1]
  • We have N bins

Problem Goal: We want to distribute the items into N bins such that all items end up in a bin, and the distribution is as uniformly distributed as possible (e.g. variance of total bin weight across bins goes to 0).

It seems like it's not exactly bin packing, since the optimization strategy is to minimize variance, rather than minimize the number of bins. Though it seems like maybe a reasonable approximation would be to just make the bin capacity the average item weights.

EDIT 1: It looks like one paper has referred to this as "load redistribution" but it doesn't seem to map exactly. Minimizing the makespan seems to imply that the distribution will be uniform, but I can't map the time/cost aspect easily (time == bucket, cost == 0?). "Load rebalancing" also doesn't seem to be a common phrasing.

$\endgroup$
3
  • 4
    $\begingroup$ Even with two bins the problem is NP-hard, by a trivial reduction from partition. When you say "trying to solve", what more specifically do you mean? $\endgroup$
    – Neal Young
    Commented Oct 18, 2022 at 19:27
  • $\begingroup$ Ah, let me rephrase. The purpose behind this question is so I can get some pointers as to where to start looking for how others have reasoned or solved the problem. For example, if there's a name for the problem, I'll probably start searching through research papers with that term. I just want to understand what the current state-of-the-art is since it seems to be a fairly interesting practical problem as well (i.e. how do you distribute steady-state work across various workers). $\endgroup$
    – Lycus
    Commented Oct 18, 2022 at 19:55
  • 1
    $\begingroup$ I see what you mean by partitioning: en.wikipedia.org/wiki/Partition_problem ... that seems like exactly what I was looking for! $\endgroup$
    – Lycus
    Commented Oct 18, 2022 at 22:15

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.