Computational Complexity of Air Travel Planning

Oof.

I had a brainbuster of a time earlier this year when I had to enumerate all possible valid schedules at a university... and this makes it look like an absolute cakewalk.

I'd be interested in reading this if it was easier to read. It's like one of those blogs where they're like "TOP 100 THINGIES!!!" and it's 100 pages, each page with 1 thingy. Thanks, but no thanks.

Click on the: "Download presentation in PDF format" link on the landing page (http://www.demarcken.org/carl/papers/ITA-software-travel-com...)

Very general; not much information. Should be useful to beginning undergrads.

It's about the complexity of the problem, not the implementation.

At least I found it interesting. I had no idea it would be this much work to get these seemingly basic routes worked out.

The ticket-price-routing problem is not new, even if it is interesting. There was an article on HN a few months ago, IIRC, talking about how ITA uses tens of thousands of lines of Common Lisp, with hand-tuned assembly, to get their optimization queries to finish within their tight space (given the huge set of possible combinations) and time bounds.

My point was that the presentation's slides are very cursory in their treatment.