Monday, April 24, 2017

Packing Books Into Boxes

As frequently as I've moved apartments in my life, I ought to be better than I am at packing up books. Taping down the flaps on a box, I'm apt to think: Might I have gotten more books in here if I'd done it differently? After so many years, why don't I have a system for this?

Apparently I'm not the only person who feels this way. Here's a moving company that offers advice for packing books—from the comments online, you can tell that book-packing vexes people.

"A constant puzzle with every box": that actually describes pretty well the abstract version of this problem, known as the three-dimensional bin-packing problem. A research article on the problem says that "The problem is strongly NP-hard and extremely difficult to solve in practice." Even the one-dimensional version of the problem is NP-hard.

To give a flavor of the subject, here's a snippet from the research article giving an approximate algorithm:

Right—why didn't I think of that?

For a much friendlier tour of the problem, click here.

I wonder if researchers have ever studied the book packing problem—that is, bin packing in the case where the bins are all 'book-shaped.' Conversely, perhaps the mathematicians who study bin packing might be able to learn something by talking to people who pack books for a living! Anyway here are a couple of videos for packing books. In common with some of the mathematical approaches I saw, both videos use strategies of pre-sorting the books and recursively creating layers. Check back the next time you need to pack up a library.

No comments: