BOS-SFO Trip Study: The Complexity of Airfare Search (2010)

From the page:

The problem of finding and pricing flights in response to a user's search request may not seem particularly difficult. However, any serious attempt to find the best solutions to a user's search unveils the true complexity of the problem, which is staggering. First, we'll give a simplified, but hopefully intuitive, back-of-the-envelope explanation and then we'll look at a specific example with some real numbers from an actual query that our QPX search engine performed.