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!
And what is the height of the shelf in the supermarket?
Hi John. I believe this is the story.
http://datagenetics.com/blog/august12014/index.html
Thanks.
I’ve seen the letter the letter the company sent back to the person with the naive solution, or at least what is reported to be the letter. Maybe it’s not real. But I haven’t been able to find it again.
Here’s the letter
https://www.reddit.com/r/rootsofprogress/comments/fe2s3b/letter_from_a_cat_food_company_to_a_math/
Thanks. That’s what I remember.
Ahhh, yes! I do recall reading that as well. Nice find Steve .
I’ve always loved that can story. It matches up well with my experience in product development, which could be seen as a very complicated optimization problem, where often you need to spend time and effort figuring out what are the most important things to optimize.