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.

Improve this question
$\endgroup$
3
  • 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, 2012 at 0:03
  • $\begingroup$ I saw this algorithm on wikipedia: en.wikipedia.org/wiki/Partition_problem#The_greedy_algorithm $\endgroup$
    – Masood_mj
    Oct 6, 2012 at 0:55
  • $\begingroup$ Yes. that's a heuristic though. I assume you want an algorithm with precise guarantees ? $\endgroup$
    – Suresh Venkat
    Oct 6, 2012 at 6:29

0

Reset to default

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.