Naive modeling

In his book The Algorithm Design Manual, Steven Skiena has several sections called “War Stories” where he talks about his experience designing algorithms for clients.

Here’s an excerpt of a story about finding the best airline ticket prices.

“Look,” I said at the start of the first meeting. “This can’t be so hard. Consider a graph … The path/fare can be found with Dijkstra’s shorted path algorithm. Problem solved!” I announced waving my hand with a flourish.

The assembled cast of the meeting nodded thoughtfully, then burst out laughing.

Skiena had greatly underestimated the complexity of the problem, but he learned, and was able to deliver a useful solution.

This reminds me of a story about a calculus professor who wrote a letter to a company that sold canned food explaining how they could use less metal for the same volume by changing the dimensions of the can. Someone wrote back thanking him for his suggestion listing reasons why the optimization problem was far more complicated than he had imagined. If anybody has a link to that story, please let me know.

Related post: Bring out your equations!