the partition problem in action

Yesterday I visited Agecroft Hall, one of the niftiest places I’ve been in Richmond. A large number of people showed up for the 2pm manor tour (there were about 20 people), and one of the tour guides struggled to partition us into two equally-sized tour groups without splitting up any of the families/groups. I was so excited to see the partition problem in action that I almost said something really nerdy (I didn’t).

The tour guide partitioned us into two rather lopsided groups. Although the partition problem is NP-complete, it shouldn’t have been all that tough to optimally solve the Agecroft Hall instance of 20 people. I enjoyed the tour anyway.

[Partition problem instance = set of integers. Can S be partitioned into two subsets such that the sum of the numbers in the first subset equals the sum of the numbers in the second subset?]

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: