The Algorithm Design Manual Second Edition

8.5

The Partition Problem

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 is simplest to divide the shelf

into three regions and assign each region to one worker.

But what is the fairest way to divide up the shelf? If all books are the same

length, the job is pretty easy. Just partition the books into equal-sized regions,

100 100 100

| 100 100 100 | 100 100 100

so that everyone has 300 pages to deal with.

But what if the books are not the same length? Suppose we used the same

partition when the book sizes looked like this:

100 200 300

| 400 500 600 | 700 800 900

I, would volunteer to take the first section, with only 600 pages to scan, instead of

the last one, with 2,400 pages. The fairest possible partition for this shelf would be

100 200 300 400 500

| 600 700 | 800 900

where the largest job is only 1,700 pages and the smallest job 1,300.

In general, we have the following problem:

Problem: Integer Partition without Rearrangement

Input: An arrangement S of nonnegative numbers

{s

1

, . . . , s

n

} and an integer k.

Output: Partition S into k or fewer ranges, to minimize the maximum sum over all

the ranges, without reordering any of the numbers.

This so-called linear partition problem arises often in parallel process. We seek

to balance the work done across processors to minimize the total elapsed run time.

---

8 . 5

T H E P A R T I T I O N P R O B L E M

295

The bottleneck in this computation will be the processor assigned the most work.

Indeed, the war story of Section

7.10

(page

268

) revolves around a botched solution

to this problem.

Stop for a few minutes and try to find an algorithm to solve the linear partition

problem.

A novice algorist might suggest a heuristic as the most natural approach to

solving the partition problem. Perhaps they would compute the average size of

a partition,



n

i=1

s

i

/k, and then try to insert the dividers to come close to this

average. However, such heuristic methods are doomed to fail on certain inputs

because they do not systematically evaluate all possibilities.

Instead, consider a recursive, exhaustive search approach to solving this prob-

lem. Notice that the kth partition starts right after we placed the (k

− 1)st divider.

Where can we place this last divider? Between the ith and (i + 1)st elements for

some i, where 1

≤ i ≤ n. What is the cost of this? The total cost will be the larger

of two quantities—(1) the cost of the last partition



n

j=i+1

s

j

, and (2) the cost of

the largest partition formed to the left of i. What is the size of this left partition?

To minimize our total, we want to use the k

− 2 remaining dividers to partition the

elements