Question

Give an algorithm that minimizes the maximum load of bins for the following description:

We are given a list of n items with sizes s1, 82,. . , Sn A sequential bin packing of these at in sad ins (That is, each bin has items si, si+1,. , s, for some indices i < j.) Bins have unbounded capacities. The load of a bin is the sum of the elements in it. Give an algorithm that determines a sequential packing of n items into k bins for which the maximum load of a bin is minimized. Analyze the tme- complexity and space-complexity

Answer 1

We can solve the problem using binary search.

First of all,let S denote the sum of all elements. Then the maximum load for any bin lies in the range [0, S]. Now lets look at a slightly different problem. Can we check whether a distribution exists where the maximum load is S1 which belongs to [0,S]. If we can check whether such a distribution exists or not, then we can binary search for the optimum S1 in the range [0,S1] and find the minimum S1 for which a distribution exists.

Algorithm:

Lets define two functions,

distributionExist(items , maxLoad)

{

    1. Iterate over items in sequential order and keep assigning them to the current bin while the load on currentbin is less than or equal to maxLoad

2. If the current item cannot be assigned to current bin, move to the next bin which will now become the current bin

3. If there is no other bin left but there are still items left, this means no distribution is possible , return false

4. Else if the items are exhausted , then a distribution is possible , return true

}

getOptimumLoad(items){

   1. rangeStart = 0 , rangeEnd = S(sum of all items)

   2. Binary search from rangeStart to rangeEnd to find the minimum load for which a distribution exist.

3. If a distribution exist for a load L , we search in the left half of the range , else we search in the right half of the range.

}

Space Complexity = O(n) for storing n items

Time Complexity = O(n*log(S))

log(S) because we binary search for the range [0,S] and for each element in the binary search algorithm we run the distributionCheck function which has complexity of O(n) and thus O(n*log(S))