Cheap and Secure Web Hosting Provider : See Now

ordered uniform distribution

, , No Comments
Problem Detail: 

We are given $n$ objects with individual weights $w_1 , w_2 , \ldots , w_n$ and $m$ buckets in which these objects are to be inserted but in order. Here order means if object $i$ goes in bucket $m_i$ and if object $j$ goes in bucket $m_j$ then if $i < j$ then $m_i \le m_j$. Objective of the problem is the minimize the weight (sum of weight of objects in the bucket) of the bucket which has the maximum weight (amongst all buckets) in such a distribution.

Asked By : eager
Answered By : A.Schulz

Here is a solution for the decision version of your problem, where you give all bins a maximum total weight they can hold.

You go through your objects in order and assign them to the bins. There is no reason to move one object to the next bin if it fits into the actual bin. So always fill the current bin as much as possible before go over to the next bin. This greedy strategy will always be optimal.

You can now turn your decision problem into an optimization problem. For example with the technique called parametric search.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57884

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback