0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ There's no "simple greedy algorithm" for the partition problem if you want to solve it exactly in polynomial time $\endgroup$ – Suresh Venkat Oct 6 '12 at 0:03
  • $\begingroup$ I saw this algorithm on wikipedia: en.wikipedia.org/wiki/Partition_problem#The_greedy_algorithm $\endgroup$ – Masood_mj Oct 6 '12 at 0:55
  • $\begingroup$ Yes. that's a heuristic though. I assume you want an algorithm with precise guarantees ? $\endgroup$ – Suresh Venkat Oct 6 '12 at 6:29

Your Answer

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

Browse other questions tagged or ask your own question.