<p>Having a set of numbers $S={s_i}$, I want to assign them to bins, $b_i$, such that the sum of items on bins follow a specific distribution. </p>

<p>For two bins and uniform distribution, this problem is similar to the partition problem. I know there is a simple greedy algorithm for that but I could not generalize it for my problem.</p>

CC BY-SA 3.0
2012-10-06T00:03:09.810Z
There's no "simple greedy algorithm" for the partition problem if you want to solve it exactly in polynomial time
Suresh Venkat
CC BY-SA 3.0
2012-10-06T00:55:47.273Z
I saw this algorithm on wikipedia: http://en.wikipedia.org/wiki/Partition_problem#The_greedy_algorithm
Masood_mj
CC BY-SA 3.0
2012-10-06T06:29:13.323Z
Yes. that's a heuristic though. I assume you want an algorithm with precise guarantees ?
Suresh Venkat
<ds.algorithms><approximation-algorithms><packing><greedy-algorithms><partition-problem>
Partitioning based on distribution
Masood_mj
# Partitioning based on distribution

(Asked by: username_0 on 2012-10-05)

Having a set of numbers $S={s\_i}$, I want to assign them to bins, $b\_i$, such that the sum of items on bins follow a specific distribution.

For two bins and uniform distribution, this problem is similar to the partition problem. I know there is a simple greedy algorithm for that but I could not generalize it for my problem.

**Tags:** ds.algorithms, approximation-algorithms, packing, greedy-algorithms, partition-problem

> **Comments:**
> **username_1**: There's no "simple greedy algorithm" for the partition problem if you want to solve it exactly in polynomial time  
> **username_0**: I saw this algorithm on wikipedia: http://en.wikipedia.org/wiki/Partition_problem#The_greedy_algorithm  
> **username_1**: Yes. that's a heuristic though. I assume you want an algorithm with precise guarantees ?  

---

## 0 answers

