A given arrangement S of non-negative numbers and an integer k.
Output: Partition S into k ranges, so as to minimize the maximum sum over all the ranges. This so-called linear partition problem arises often in parallel processing, since we seek to balance the work done across processors so as to minimize the total elapsed run time. Indeed, the war story of Section 
revolves around a botched solution to this problem.
revolves around a botched solution to this problem.Application - Suppose that three workers are given the task of scanning through a shelf of books in search of a given piece of information. To get the job done fairly and efficiently, the books are to be partitioned among the three workers. To avoid the need to rearrange the books or separate them into piles, it would be simplest to divide the shelf into three regions and assign each region to one worker.
But what is the fairest way to divide the shelf up? If each book is the same length, say 100 pages, the job is pretty easy. Just partition the books into equal-sized regions,
so that everyone has 300 pages to deal with.
But what if the books are not the same length?
1 comments:
First find the sum of all the numbers in S, divide it by k and store it in b.
Our aim now to divide S, so that sum should be as close to b as possible, for that purpose purpose we'd define a range b - k/2 and b + k/2. Now start scanning the array from start and keep adding to sum, if the sum falls in range previously mentioned, try to get closer to b by removing last array element or by adding the next one, whichever is closer should be end of first partition. On the similar lines partition rest of array.
Though this does not guarantee the fair partitions but I think if difference between array elements is not much, it would lead to near fair distribution.
I hope it made sense.
Post a Comment