First page Back Continue Last page Overview Graphics

Computational Complexity of Air Travel Planning


Notes:

This document is an annotated set of slides on the computational complexity of air travel planning. The goal is to give somebody with an undergraduate level computer science background enough information to understand why air travel planning is an interesting and especially difficult problem. It provides a basic introduction to the air travel planning problem and then presents a variety of original computational complexity results as well as some related demos. The complexity slides assume a basic familiarity with formal languages, computational complexity and computability, but the introduction to the problem should be accessible without this.

ITA Software produces search and optimization software for the travel industry. Our search engines power popular web sites such as Orbitz and Cheap Tickets; airline web sites such as America West, Continental Airlines and Alaska Airlines; computer reservation systems (CRS/GDSes) used by travel agencies, such as Galileo; and various travel agencies. ITA was founded by MIT computer scientists and is located adjacent to MIT in Cambridge, MA.