<p>I'm trying to find reading material on a particular problem I'm interested in, but I don't know the terms to search.</p>
<p>Problem assumptions/definitions:</p>
<ul>
<li>We have finite number of items I with weights [0, 1]</li>
<li>We have N bins</li>
</ul>
<p>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).</p>
<p>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.</p>
<p>EDIT 1: It looks like one paper has referred to this as &quot;load redistribution&quot; 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?).  &quot;Load rebalancing&quot; also doesn't seem to be a common phrasing.</p>

CC BY-SA 4.0
2022-10-18T19:27:51.847Z
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?
Neal Young
CC BY-SA 4.0
2022-10-18T19:55:52.720Z
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).
Lycus
CC BY-SA 4.0
2022-10-18T22:15:38.863Z
I see what you mean by partitioning: https://en.wikipedia.org/wiki/Partition_problem ... that seems like exactly what I was looking for!
Lycus
<cc.complexity-theory><ds.algorithms><reference-request><optimization><packing>
Uniformly redistributing items across bins. What problem is this?
Lycus
# Uniformly redistributing items across bins. What problem is this?

(Asked by: username_0 on 2022-10-18)

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.

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, optimization, packing
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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).  
> **username_0**: I see what you mean by partitioning: https://en.wikipedia.org/wiki/Partition_problem ... that seems like exactly what I was looking for!  

---

## 0 answers

