Subscribe
Subscribe
MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
Logo IMG
HOME > PAST ISSUE > March-April 2002 > Article Detail

COMPUTING SCIENCE

The Easiest Hard Problem

Brian Hayes

So What's the Problem?

Here is a slightly more formal statement of the partitioning problem. You are given a set of n positive integers, and you are asked to separate them into two subsets; you may put as many or as few numbers as you please in each of the subsets, but you must make the sums of the subsets as nearly equal as possible. Ideally, the two sums would be exactly the same, but this is feasible only if the sum of the entire set is even; in the event of an odd total, the best you can possibly do is to choose two subsets that differ by 1. Accordingly, a perfect partition is defined as any arrangement for which the "discrepancy"—the absolute value of the subset difference—is no greater than 1.

Try a small example. Here are 10 numbers—enough for two basketball teams—selected at random from the range between 1 and 10:

2 10 3 8 5 7 9 5 3 2

Can you find a perfect partition? In this instance it so happens there are 23 ways to divvy up the numbers into two groups with exactly equal sums (or 46 ways if you count mirror images as distinct partitions). Almost any reasonable method will converge on one of these perfect solutions. This is the answer I stumbled onto first:

(2 5 3 10 7) (2 5 3 9 8)

Both subsets sum to 27.

This example is in no way unusual. As a matter of fact, among all sets of 10 integers between 1 and 10, more than 99 percent have at least one perfect partition. (To be precise, of the 10 billion such sets, 9,989,770,790 can be perfectly partitioned. I know because I counted them—and it wasn't easy.)

Maybe larger sets are more challenging? With a list of 1,000 numbers between 1 and 10, working the problem by pencil-and-paper methods gets tedious, but a simple computer program makes quick work of it. A variation on the two-bullies algorithm does just fine. First sort the list of numbers according to magnitude, then go through them in descending order, assigning each number to whichever subset currently has the smaller sum. This is called a greedy algorithm, because it takes the largest numbers first.

Figure 2. Greedy algorithm . . .Click to Enlarge Image

The greedy algorithm almost always finds a perfect partition for a list of a thousand random numbers no greater than 10. Indeed, the procedure works equally well on a set of 10,000 or 100,000 or a million numbers in the same range. The explanation of this success is not that the algorithm is a marvel of ingenuity. Lots of other methods do as well or better.

A particularly clever algorithm was described in 1982 by Narendra Karmarkar and Richard M. Karp, who were then both at the University of California, Berkeley. It is a "differencing" method: At each stage you choose two numbers from the set to be partitioned and replace them by the absolute value of their difference. This operation is equivalent to deciding that the two selected integers will go into different subsets, without making an immediate commitment about which numbers go where. The process continues until only one number remains in the list; this final value is the discrepancy of the partition. You can reconstruct the partition itself by working backward through the series of decisions. In the search for perfect partitions, the Karmarkar-Karp procedure succeeds even more often than the greedy algorithm.

At this point you may be ready to dismiss partitioning as just a wimpy problem, unworthy of the designation NP-complete. But try one more example. Here is another list of 10 random numbers, chosen not from the range 1 to 10 but rather from the range between 1 and 210, or 1,024:

771 121 281 854 885 734 486 1003 83 62

Figure 3. Karmarkar-Karp algorithm . . .Click to Enlarge Image

This set does have a perfect partition, but there is just one, and finding it takes a little persistence. The greedy algorithm does not succeed; it gets stuck on a partition with a discrepancy of 32. Karmarkar-Karp does slightly better, reducing the discrepancy to 26. But the only sure way to find the one perfect partition is to check all possible partitions, and there are 1,024 of them.

If this challenge is still not daunting enough, try 100 numbers ranging up to 2100, or 1,000 numbers up to 21000. Unless you get very lucky, deciding whether such a set has a perfect partition will keep you busy for quite a few lifetimes.




comments powered by Disqus
 

EMAIL TO A FRIEND :

Of Possible Interest

Computing Science: Belles lettres Meets Big Data

Technologue: Quantum Randomness

Technologue: The Quest for Randomness

Subscribe to American Scientist