6 September 2006: Windy

Two blogs in one day when I'm writing up?

Well, having just mailed two further chapters in for review, I thought it might be a good opportunity to have a look at the matching method I used to tie together the ACM and Citeseer paper sets and see if I could improve it a little. I won't explain it since it'll be very boring for you (it's quite boring for me, and I actually enjoy this kind of tedious pattern-matching stuff) but it does continue to give me ample opportunities to look at the titles of obscure academic papers that nobody has ever cited and quite possibly nobody will ever read again.

My point is this: some of the titles are strangely, glorious bizarre. As a random choice, currently rolling up the screen in front of me are papers titled "A bump in the stack encryptor for MS-DOS systems" (I'm sure it'd be a bump in the stack for anyone) and "A 2-(22,8,4) Design Cannot Have a 2-(10,4,4) Subdesign" (I never said it could).

But my favourite, and the real reason for blogging twice in a day, is the wonderfully-titled paper "A 3/2-approximation algorithm for the Windy Postman Problem." How could it not grab my attention with a name like that? The first thing I love is the way the title naturally assumes that I know what the Windy Postman Problem is, and why I should therefore be excited at an approximation algorithm costing only three shillings and two pence. Sadly, of course, I had no idea what the Windy Postman Problem was, but as the matches continued to roll up the screen, my imagination began to run riot. What were they talking about? The thought process ran roughly as follows:

- It's got to be about farting. Kind of like Windy Miller from Camberwick Green, too many beans, heh-heh-heh-Beavis. (Incidentally, why aren't you surprised that my mind went to the farting scenario first?)
- Is it postmen having problems with wind? Or postmen who suffer from wind having problems in society? Maybe it's a problem with airmail?
- Maybe the wind is so strong it blows the letters out of the postman's hand and he has to go and collect them all again?
- Maybe he needs a van, like the UPS guys. Except without the brown socks.
- Hm, yes. It's got to be about strong wind causing problems for the postman in his delivery duties. It's got to be about the losing-the-letters-and-having-to-find-them-again thing. While farting.

Not even close. Apparently it's one of those simple-sounding problems that we used to occasionally come across at school, like the travelling salesman problem: essentially, what's the quickest route to make sure the postman visits every street in a city at least once? That's the general 'Chinese Postman Problem'. (We have a problem with Chinese postmen now?) Variations include the use of one-way streets as part of the problem. The Windy Postmen have the additional problem that while all the streets are two-way, some are more easily traversable in one direction than the other (because there's a strong tropical wind out there of course), so there's a trade-off to be made between short, costly routes and longer, wind-backed paths. And the people who wrote the paper weren't talking old money, the 3/2 is to do with how long it takes to calculate an approximation for the best path.

Still, it was fun while it lasted. Meantime the matching algorithm spots another one: "A Case Study on the Mergeability of Cases with a Partial-Order Planner" goes into the database. What an afternoon I'm having.

Elsewhere, future-movie-critic-and-eldest-nephew Matt continues to dazzle with unexpected observations. When asked by our reporter to name his favourite vegetable, his second answer (his first was 'fish fingers') was 'broccoli' (which is strange enough in itself) and when asked why he replied 'because it looks like trees'.

He started school yesterday. I doubt they'll know what's hit them.

Postscript: Googling on 'windy postman problem' brings even weirder stuff to light. I just found a paper that states: "Eulerian graphs and trees are windy postman perfect." Intriguing, baffling and poetic all at the same time.