Biblioptimization

Friday, 14 September 2007 — 10:46am | Computing, Literature, Mathematics, Science

As it is, I’m already very indecisive when it comes to shopping for books. But if you really want to trap me at a display case for nigh on an hour, toss in an NP-hard combinatorial problem (my non-mathematical readers: refer to this simple illustration) and I’m done for.

The scenario: I won a $250 book prize for an essay I wrote last year (something to do with moral culpability in Adam Bede, if I remember correctly), redeemable for anything published by the University of Alberta Press. Because I insist on getting my money’s worth, we can formulate this as Objective 1: Spend $250 on books.

Oh, but it doesn’t stop there. You see, when I went to go pay the UAP a visit and make my book selection, I travelled by bicycle, which inadvertently introduced a second dimension, making this a doubly-constrained knapsack problem. Objective 2: Select books of appropriate size and weight that will fit in my backpack without getting wrecked, so I can actually carry them home on a bike.

Of course, I wasn’t just going to pick any set of books I see just so I could use up the entirety of the book prize without having to pay extra for going over. Objective 3: Maximize the sum of the value-functions assigned to the contents of the books selected. (In plain English: “Pick interesting books that I will actually read.”)

My solution?

Deep Alberta: Fossil Facts and Dinosaur Digs (John Acorn) — There was a time when I was the dinosaur kid to end all dinosaur kids. It was before Jurassic Park, too. I went to the Royal Tyrell Museum so often in my youth that I wondered if I had this book already, but it was only published this year, so I guess not; it probably looked familiar because I was just at the museum last month.

North of Everything: English-Canadian Cinema Since 1980 (William Beard and Jerry White, eds.) — I had a hard time deciding between this one and Great Canadian Film Directors (George Melnyk, ed.), which is less historical and seems to have a lot more depth from the critical side of things. But this volume is the one that has a whole chapter on animation by OIAF director Chris Robinson, another chapter about Manitoban animation alone, two on David Cronenberg, and much, much more.

Persistence of Double Vision: Essays on Clint Eastwood (William Beard) — Self-explanatory. Published in 2000, it predates Eastwood’s most interesting period as a director (Mystic River, Million Dollar Baby and Letters from Iwo Jima), but it will at least draw me to some of the earlier films I missed.

Forging Alberta’s Constitutional Framework (Richard Connors and John M. Law, eds.) — Once a hack, always a hack.

Paddling with the Current: Pierre Elliott Trudeau, Étienne Parent, liberalism, and nationalism in Canada (Claude Couture) — Ethnic nationalism in Quebec, collective and individual rights, and the paradoxes of multiculturalism? Sold.

Propaganda and Censorship During Canada’s Great War (Jeffrey A. Kashen) — I’m usually more interested in propaganda from an art and design point of view than a sociohistorical one, but I’ve also harboured a soft spot for state control of information ever since the first time I watched Brazil. The Canadian focus is a bonus, as I simply don’t know much about it.

I Was There: A century of alumni stories about the University of Alberta, 1906-2006 (Ellen Schoeck) — The UAP’s contribution to the centenary hullabaloo, this was an easy pick, and the first one I pulled off the shelf. I very nearly bought it right away when the University Bookstore stocked it last year. Evidently, free things come to those who wait.

The total cost came to $250.85. They let me get away with the eighty-five cents.

There’s probably already a name for this already, but I don’t know it. So I think I’ll call this the Book Prize Redemption Problem, or in the interest of generality, the (n,m)-Gift Certificate Problem for the case (2,1). Correct me if I’m wrong, but I don’t think it’s quite the same as an n-dimensional knapsack problem, because we’re also trying to do m unbounded maximizations. I leave the construction of an efficient polynomial-time approximate algorithm as an exercise for the reader.

Previous:
Next:

submit to reddit

One rejoinder to “Biblioptimization”