ColloquiaCarl de Marcken - Wednesday, March 6

[Margery Ishmael]

Date:  Wednesday, March 6
Time:	2:30 p.m.
Place: Ryerson 251

Speaker: Carl de Marcken, Chief Scientist, ITA Software

Title: The Computational Complexity of Air Travel Planning

Abstract:
At any moment there are between 2,000 and 10,000 commercial airliners in 
the sky, part of a dense network that provides more than 100,000 practical 
paths from Boston to the Bay area every day.

But the search problem faced by travel agents, that of finding a desirable 
combination of flights and fares for a given passenger's trip, is much 
harder than path planning.  In fact, the airlines' price structure is so 
rich that finding the cheapest price for a simple round-trip journey is in 
the general case undecidable.  Even if one bounds the size of solutions to 
a small number of flights there may be more than 10^20 reasonable answers 
to a simple travel query.

This talk will describe the nature of the travel planning problem from a 
computer science perspective, ranging from network properties of the 
flights to the practical and theoretical complexity of pricing.

In addition, it will sketch some new search algorithms that are a radical 
departure from the brute force methods that previously dominated the travel 
industry.  For example, we directly construct a factored graphical 
representation of the space of answers to a travel query that is very 
similar to a Bayes' net or the chart produced by a context-free 
parser.  Using this representation a graph of 250,000 nodes can encode 
10^30 or more options.  We have developed a wide range of algorithms for 
manipulating this representation, and many of our problems and solutions 
will be of interest to the Bayes' net and statistical NLP communities.

Biographical Information: Carl de Marcken is Chief Scientist of ITA 
Software, the technology powering ORBITZ. Carl has a Ph.D.  in Computer 
Science from MIT, where his research in machine learning won the 
distinguished award for best computer science thesis. Carl is the author of 
many academic articles on computational linguistics, in areas including 
unsupervised acquisition of linguistic structure.

Host: Gina-Anne Levow

*The talk will be followed by refreshments in Ryerson 255*
Persons with disabilities who may need assistance should call 773.834.8977


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margery Ishmael
Secretary to the Chairman, Department of Computer Science
The University of Chicago
1100 E. 58th Street, Chicago, IL. 60637-1581
tel. 773.834.8977  fax. 773.702.8487
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=